Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
codeIn Reply To:麻烦牛人给写数据,拜谢 Posted by:nuanran at 2006-08-02 09:51:33 #include <stdio.h> #define MAXN 1010 int mat[MAXN]; int dp[MAXN][MAXN]; int ant[MAXN][MAXN]; bool mark[MAXN][MAXN]; bool final[MAXN][MAXN]; int main() { int n,m,total,max,pmax,tmp1,tmp2,t,i,j; while(scanf("%d%d",&n,&m)&&(n||m)) { for(i=1;i<=n;i++) scanf("%d",&mat[i]); final[1][1]=0; max=total=ant[1][1]=mat[1]; for(i=2;i<=n;i++) { if(total<0) total=0; total+=mat[i]; if(total>max) max=total,final[1][i]=0; else if(total==max) final[1][i]=1; else final[1][i]=final[1][i-1]; ant[1][i]=max; } total=mat[1]; for(i=2;i<=m;i++) { total+=mat[i]; ant[i][i]=dp[i][i]=total; mark[i][i]=final[i][i]=0; } for(i=2;i<=m;i++) { max=ant[i][i]; for(j=i+1;j<=n;j++) { tmp1=dp[i][j-1]+mat[j]; tmp2=ant[i-1][j-1]+mat[j]; if(tmp1>tmp2) dp[i][j]=tmp1,mark[i][j]=mark[i][j-1]; else if(tmp1<tmp2) { dp[i][j]=tmp2; mark[i][j]=final[i-1][j-1]; } else dp[i][j]=tmp2,mark[i][j]=1; if(dp[i][j]>max) max=dp[i][j],final[i][j]=mark[i][j]; else if(dp[i][j]<max) final[i][j]=final[i][j-1]; else final[i][j]=1; ant[i][j]=max; } } if(final[m][n]) printf("No\n"); else printf("Yes\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator