DP笔记

发布于 2021-11-05  467 次阅读


内容纲要

WiDayn的DP笔记

P1077 [NOIP2012 普及组] 摆花

题目描述

小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 n 种花,从 1 到 n 标号。为了在门口展出更多种花,规定第 i 种花不能超过 a[i] 盆, 花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算,一共有多少种不同的摆花方案。

输入 #1

2 4
3 2

输出 #1

2

代码

#include<bits/stdc++.h>
using namespace std;

int n,m,a[110],f[110];
int main()
{
    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    f[0] = 1;
    for(int i = 1; i <=n; i++){
        for(int j = m; j >= 0; j--){
            for(int k = 1; k <= a[i]; k++){
                if(j - k >= 0) f[j] = (f[j] + f[j - k]) % 1000007; //前k排的数量相加 % 1000007
            }
        }
    }
    printf("%d", f[m]);
    return 0;
}

思路

其实个人感觉有点像走台阶(一次跳一格或者两格的那个), 在判断的时候都是要考虑该位置的前N个情况。

DP时从后向前考虑有多少种情况可以刚好到达那里。

考虑到0个位置的时候只有1种摆法就是什么都不放,所以F[0]为1。

之后做的是一个累加操作,每次增加都代表从j-k位置经过k个花盆到达j位置。

以样例为例:

F[i] 0 1 2 3 4
val  1 0 0 0 0

一轮循环过后

F[i] 0 1 2 3 4
val  1 1 1 1 0

两轮循环过后

F[i] 0 1 2 3 4
val  1 1 1 2 2

取的当然就是F[4]的最终值,表示的是能以两种花盆到达F[4]的所有情况。

P3842 [TJOI2007]线段

题目描述

在一个$$ n \times n $$的平面上,在每一行中有一条线段,第 ii 行的线段的左端点是$$(i, L{i})(i,Li) $$,右端点是$$(i, R{i})(i,Ri) $$。

你从 $$(1,1)$$ 点出发,要求沿途走过所有的线段,最终到达$$ (n,n)$$点,且所走的路程长度要尽量短。

更具体一些说,你在任何时候只能选择向下走一步(行数增加$$1$$)、向左走一步(列数减少 $$1$$)或是向右走一步(列数增加 $$1$$)。当然,由于你不能向上行走,因此在从任何一行向下走到另一行的时候,你必须保证已经走完本行的那条线段。

输入 #1

6
2 6
3 4
1 3
1 2
3 6
4 5

输出 #1

24

代码

#include<bits/stdc++.h>
using namespace std;

int disLeft(int x, int l, int r){
    return abs(x - r) + abs(r - l);
}

int disRight(int x, int l, int r){
    return abs(x - l) + abs(r - l);
}

int main(){
    int n; cin>>n;
    int bl = 1, br = 1; //初始坐标(1,1)
    int l,r; int suml = 0, sumr = 0; //初始左累加,右累加
    for(int i = 0; i < n; i++){
        cin>>l>>r;
        int bsuml = suml, bsumr = sumr; //设置一个变量暂存
        suml = min(disLeft(bl, l, r) + bsuml, disLeft(br, l, r) + bsumr); //状态转移
        sumr = min(disRight(bl, l, r) + bsuml, disRight(br, l, r) + bsumr);
        bl = l, br = r; //记录这一行的左右端点,下一次循环时读取新的左右端点
    }
    suml = min(disLeft(bl, n, n) + suml, disLeft(br, n, n) + sumr); //将终点(n,n)看作左右端点都为n的新的一行
    sumr = min(disRight(bl, n, n) + suml, disRight(br, n, n) + sumr);
    printf("%d", min(suml, sumr) + n - 1); //先去左端点和右端点最小值,再加上上下移动n-1次
}

思路

麻了,这题写了贼久,一直没注意到在算sumr的时候suml是已经被改动过的了,一直在怀疑自己哪里做错了。

转移方程:
$$
这一行的左端点 = min(上一行的左端点到这一行的 + 上一行左端点的累加值, 上一行的右端点到 + 上一行右端点的累加值)
$$
对于右端点也是同理。

而计算距离时,对于左端点,无论上一行的端点是什么状态,都是先到右端点(经过),再到左端点,即$$ abs(x - r) + abs(r - l) $$

对于右端点也同理。

感觉DP题细节还是很多的,在开始做之前要想清楚有几种情况(第一次想的时候甚至分出了6种情况= =,导致代码极其复杂最后WA了)


不爱嘉然小姐十年了。十年里,爱过的每个人都像她。