动态规划—洛谷 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;
}