洛谷P1107 & BZOJ1270 [BJWC2008]雷濤的小貓

一道DP。

給你一個矩陣裡面有很多數，你需要從上往下找到一種跳躍方法使得經過的點的價值之和最大。

具體題面見鏈接

洛谷P1107

BZOJ1270

很明顯是一個二維的DP。

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

int N, H, Delta;
int t[2020][2020];//t為原始生成的圖，同時也作為保存狀態的二維數組
int dp[2020];//dp[i]表示高度為i時取得的最大價值

inline void input(){//輸入數據並存為圖，存圖方式如上圖圖片
    scanf("%d%d%d", &N, &H, &Delta);
    for(register int i = 1; i <= N; i ++){
        int num;
        scanf("%d", &num);
        for(register int j = 1; j <= num; j ++){
            int temp;
            scanf("%d", &temp);
            t[temp][i]++;
        }
    }
}

int main(){
    input();
    for(register int i = 1; i <= H; i ++){
        for(register int j = 1; j <= N; j ++){
            if(i <= Delta){//當高度比Delta小時，當前狀態只能從同一列的上一個狀態轉移
                t[i][j] += t[i - 1][j];//
                dp[i] = max(dp[i], t[i][j]);//當前高度能取得的最大價值為當前行所有狀態的最大值
                continue;
            }
            t[i][j] += max(dp[i - Delta], t[i - 1][j]);//普通的狀態轉移方程
            dp[i] = max(dp[i], t[i][j]);//同時要更新當前高度能取得的最大價值
        }
    }
    printf("%d\n", dp[H]);
    return 0;
}

 混搭碼風，求諒解。