问题描述
热爱电子娱乐的同学们对于技能树一定不陌生.就是说,要先学习低级的垃圾技能,特定的几个垃圾技能学会了,才能学习更强的技能.比如说,要先学火球术和烈火墙,才能学习地狱烈焰.科技树也是一样.要先研究出电力和内燃机,才能研究工业学.那么,现在我们把问题简化
14 15 4 3 23
33 33 76 2
2 13 11
22 23
31
这是一个技能树(或者科技树).格子上的数,是威力值.要先学会第一排第二个和第三个,才能学会第二排的第二个.每个技能学习的前提都是左上和右上的两个技能.假设现在有一个第一层有N个技能的技能树,而且技能点是有限的,只能学习M个技能,我们想知道最大的威力值之和是多少。
【输入数据】
第一行两个数N和M,如题所述
之后N行,第i行,有n+1-i个数.表示一个技能树。
【输出数据】
输出一个数,表示最大威力值之和。
【输入样例】
4 5
1 1 1 1
1 2 1
1 1
1
【输出样例】
6
【数据规模】
对于40%的数据,N<=10
对于100%的数据,N<=50,M<=500,所有数据都在longint之内.
我定义的状态是
f[i][j][k]表示第i列，取j行，前面一共取了k个取得的最大值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 55
using namespace std;
int map[MAXN][MAXN];
int f[MAXN][MAXN][MAXN];
int sum[MAXN][MAXN]; //第i列第1行到第j行的和
int main()
{
freopen("Test.in","r",stdin);
freopen("Test.out","w",stdout);
int i,j,k,v;
int N,M;
int maxSum = 0;
int temp;
scanf("%d %d",&N,&M);
for(i = 1;i <= N;i ++)
{
for(j = 1;j <= N+1-i;j ++)
{
scanf("%d",&map[i][j]);
}
}
for(i = 1;i <= N;i ++)
{
for(j = 1;j <= N+1-i;j ++)
{
sum[i][j] = sum[i-1][j] + map[i][j];
}
}
f[N+1][0][0] = 0;
//f[N][1][1] = map[N][1];
for(i = N;i >= 1;i --)
{
for(j = 0;j <= N-i+1;j ++)
{
for(k = j;k <= M;k ++)
{
for(v = j-1;v <= N-i+1;v ++)
{
f[i][j][k] = max(f[i][j][k],f[i+1][v][k-j]);
}
f[i][j][k] += sum[j][i];
if(maxSum < f[i][j][k])
{
maxSum = f[i][j][k];
}
}
}
}
printf("%d",maxSum);
return 0;
}状态转移应该是对的啊，WRONG到吐血！！！
跪求修正！！！先谢了！
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
