「BZOJ3997」[TJOI2015] 组合数学
Description
给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。
Input
第一行为正整数T，代表数据组数。
每组数据第一行为正整数N，M代表网格图有N行M列，接下来N行每行M个非负整数，表示此格子中财宝数量，0代表没有
Output
输出一个整数，表示至少要走多少次。
Sample Input
1
3 3
0 1 5
5 0 0
1 0 0
3 3
0 1 5
5 0 0
1 0 0
Sample Output
10
HINT
N<=1000,M<=1000.每个格子中财宝数不超过10^6
题解
最长反链=DAG最小路径覆盖
这题最长反链是个显然的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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m; int a[1005][1005]; ll f[1005][1005]; int main() { T=read(); while(T--) { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); for(int i=1;i<=n;i++) for(int j=m;j;j--) f[i][j]=max(f[i-1][j+1]+a[i][j],max(f[i-1][j],f[i][j+1])); printf("%lld\n",f[n][1]); } return 0; } |
计数器 9854627
OI 课件=>
OI 课件=>
可以解释下是怎样DP的吗？
问wt，他做过