(luogu1941) 飞扬的小鸟 (NOIP2014 TG)

发表于 分类于 ，

原题链接

一个比较综合的背包 dp.

思路:

这题基本结合了比较基础的几个背包 dp: 上升是完全背包，下降是 01 背包.

至于管道的计数，可以边计算 dp 边判定.

边界条件与转移方程参见代码.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
const int Mn(10050),Mm(1050);
const int INF(0x3f3f3f3f);
int dp[Mn][Mm]; //dp数组
int dly[2][Mn]; //y值变化量, dly[0]为下降, dly[1]为上升
int ppl[Mn],pph[Mn];    //管缝下边沿, 管缝上边沿
int ppn[Mn];    //某位置的管缝编号

int main() {
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    for(int i(0);i<n;++i) {
        scanf("%d %d",dly[1]+i, dly[0]+i);
    }
    for(int i(1);i<=k;++i) {
        int p,l,h;
        scanf("%d %d %d",&p,&l,&h);
        ppl[i] = l;
        pph[i] = h;
        ppn[p] = i;
    }
    memset(dp,0x3f,sizeof dp);      //其他的位置初始化为无穷大
    memset(dp[0],0,sizeof dp[0]);   //x=0的位置初始化为0
    int pipeCount(0);   //计算通过多少管道
    bool isPossible = true; //是否成功通过
    for(int i(1);i<=n;++i) {
        for(int j(dly[1][i-1]+1);j<=m;++j) {
            //上升转移
            dp[i][j] = min(dp[i][j],dp[i-1][j-dly[1][i-1]]+1);
            dp[i][j] = min(dp[i][j],dp[i][j-dly[1][i-1]]+1);
        }
        for(int j(m-dly[1][i-1]+1);j<=m;++j) {
            //上升触顶
            dp[i][m] = min(dp[i][m],dp[i-1][j]+1);
            dp[i][m] = min(dp[i][m],dp[i][j]+1);
        }
        for(int j(m-dly[0][i-1]);j;--j) {
            //下降转移
            dp[i][j] = min(dp[i][j],dp[i-1][j+dly[0][i-1]]);
        }
        if(ppn[i]) {
            //若x=i为管道则判定
            for(int j(1);j<=ppl[ppn[i]];++j) {  //上下不是管缝的位置清空
                dp[i][j] = INF;
            }
            for(int j(pph[ppn[i]]);j<=m;++j) {
                dp[i][j] = INF;
            }
            bool isOver = true; //是否无法通过
            for(int j(ppl[ppn[i]]+1);j<=pph[ppn[i]]-1;++j) {
                if(dp[i][j]!=INF) {
                    isOver = false;
                    break;
                }
            }
            if(isOver) {
                printf("0\n%d",pipeCount);
                isPossible = false;
                break;
            } else {
                ++pipeCount;
            }
        }
    }
    if(isPossible) {
        printf("1\n");
        int ans(INT_MAX);
        for(int i(1);i<=m;++i) {
            ans = min(ans,dp[n][i]);
        }
        printf("%d",ans);
    }
    return 0;
}