mringg的天空,自由,自在  
日历
<2010年2月>
31123456
78910111213
14151617181920
21222324252627
28123456
78910111213
统计
  • 随笔 - 6
  • 文章 - 0
  • 评论 - 0
  • 引用 - 0

导航

常用链接

留言簿

随笔分类

随笔档案

相册

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
 1#include<cstdio>
 2#include<cstring>
 3#include<iostream>
 4using namespace std;
 5
 6const int dir[2][4]={{-1,-1,0,0},{-1,0,-1,0}};
 7int F[120][60][60],a[60][60];
 8int n,m;
 9int Max(int x,int y)
10{
11    if (x>y) return x;
12    else return y;
13}

14int Min(int x,int y)
15{
16    if (x>y) return y;
17    else return x;
18}

19int main()
20{
21    scanf("%d%d",&n,&m);
22    for (int i=1;i<=n;i++)
23        for (int j=1;j<=m;j++)
24            scanf("%d",&a[i][j]);
25    memset(F,0,sizeof(F));
26    int x;
27    for (int k=2;k<=n+m;k++)
28        for (int i1=1;i1<=Min(n,k-1);i1++)
29            for (int i2=1;i2<=Min(n,k-1);i2++)
30            {
31                x=a[i1][k-i1]+a[i2][k-i2];
32                if (i1==i2) x=a[i1][k-i1];
33                for (int i=0;i<=3;i++)
34                    F[k][i1][i2]=Max(F[k][i1][i2],F[k-1][i1+dir[0][i]][i2+dir[1][i]]);
35                F[k][i1][i2]+=x;
36            }

37    printf("%d\n",F[n+m][n][n]);
38    return 0;
39}

40
posted on 2010-02-09 15:59 mringg 阅读(265) 评论(0)  编辑 收藏 引用 所属分类: 动态规划NOIP题解

只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © mringg Powered by: 博客园 模板提供:沪江博客