首页
社区
课程
招聘
信息学竞赛技能树问题求解!WRONG到吐血了
发表于: 2011-10-26 12:02 3923

信息学竞赛技能树问题求解!WRONG到吐血了

2011-10-26 12:02
3923
问题描述
热爱电子娱乐的同学们对于技能树一定不陌生.就是说,要先学习低级的垃圾技能,特定的几个垃圾技能学会了,才能学习更强的技能.比如说,要先学火球术和烈火墙,才能学习地狱烈焰.科技树也是一样.要先研究出电力和内燃机,才能研究工业学.那么,现在我们把问题简化
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直播授课

收藏
免费 0
支持
分享
最新回复 (1)
雪    币: 36
活跃值: (598)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
2
已自己解决~
是没赋初值的问题
下面是AC的程序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 60

using namespace std;

int map[MAXN][MAXN];
int f[MAXN][MAXN][505];
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 = -1;
    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];
			}
	}
                
    for(i = N;i >= 1;i --)
    	for(j = 0;j <= N-i+1;j ++)
    		for(k = 0;k <= M;k ++)
    			f[i][j][k] = -987654321;
    
    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;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\n",maxSum);
    return 0;
}

2011-10-26 15:35
0
游客
登录 | 注册 方可回帖
返回
//