动态规划—洛谷 P1941 飞扬的小鸟

洛谷 P1941 飞扬的小鸟

分析

这显然是个dp问题，在每一列中，我没有两种选择：上升或下降。
上升：在每一列中可以无限次选择上升，恰好符合完全背包问题；
下降：通过题目知道，每列只能下降一次，正是01背包问题；
顶点的特判；

状态dp[i][j]表示到达点（i，j）花费的最少时间。
当前状态（红点）可以是由其他三个状态（蓝点，粉点，绿点）转移的
∴ f[i][j]=min(f[i][j+down[i-1]],f[i-1][j-up[i-1]],f[i][j-up[i]])
其中up[i],down[i]分别表示小鸟在第i列每次上升，下降的高度。
以下是代码实现：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[10005][2004];
int up[10005], down[10005];	//在i列上升下降的距离
int x[10005], s[10005];	//管道的下边沿高度和上边沿高度
bool f[10005];	//记录第i列是否有管道
int main()
{
    memset(dp, 0x3f, sizeof dp);	//把dp置为正无穷
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n;i++)
    {
        cin >> up[i] >> down[i];
    }
    for (int i = 1; i <= k;i++)
    {
        int h;
        cin >> h;
        cin >> x[h] >> s[h];
        f[h] = 1;
    }
    for (int i = 1; i <= m;i++)
        dp[0][i] = 0;
    for (int i = 1; i <= n;i++)
    {
        for (int j = up[i] + 1; j <= m + up[i];j++)		//上升过程，完全背包
        {
            dp[i][j] = min(dp[i - 1][j - up[i]], dp[i][j - up[i]]) + 1;
        }
        for (int j = m + 1; j <= m + up[i]; j++)	//特判顶部
        {
            dp[i][m] = min(dp[i][m], dp[i][j]);
        }
        for (int j = 1; j <= m - down[i];j++)	//下降过程，01背包
        {
            dp[i][j] = min(dp[i][j], dp[i - 1][j + down[i]]);
        }
        if (f[i])	//将不能通过的点重置
        {
            for (int j = 1; j <= x[i];j++)
                dp[i][j] = dp[0][0];
            for (int j = s[i]; j <= m;j++)
            {
                dp[i][j] = dp[0][0];
            }
        }
    }
    int min1 = dp[0][0];
    for (int i = 1; i <= m;i++)
    {
        min1 = min(min1, dp[n][i]);
    }
    if (min1<dp[0][0])
    {
        cout << 1 << endl;
        cout << min1 << endl;
    }
    else
    {
        int i,j;
        for (i = n; i >= 1;i--)			//从后往前遍历，找到最后一次通过的一列
        {
            for (j = 1; j <= m;j++)
            {
                if (dp[i][j]<dp[0][0])
                    break;
            }
            if (j <= m)
                break;
        }
        int num = 0;		//记录通过的管道数
        for (j = 1; j <= i;j++)
        {
            if (f[j])
                num++;
        }
        cout << 0 << endl;
        cout << num << endl;
    }
        return 0;
}