洛谷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;
}

 混搭码风，求谅解。