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 |
那位大哥帮看看,WA得不行了#include <iostream> using namespace std; int dp[1101][1101][3],num[1101]; int max(int a,int b,int c) { if (a>b) return a>c?a:c; else return b>c?b:c; } int init (int n,int m) { int i,j; for (i=1;i<=n;i++) scanf ("%d",&num[i]); for (i=0;i<=n;i++) { dp[i][0][0]=0,dp[i][0][1]=-2000000000; for (j=1;j<=m;j++) dp[i][j][0]=-2000000000,dp[i][j][1]=-2000000000; } } int solve (int n,int m) { int i,j,temp; for (i=1;i<=n;i++) { temp=min(i,m); for (j=1;j<=temp;j++) { dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1],-2000000000); dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1],dp[i-1][j][1])+num[i]; } } return 1; } bool solution (int i,int j,int type) { if (type==0) { if (dp[i-1][j][0] == dp[i-1][j][1]) return false; if (dp[i-1][j][0]>dp[i-1][j][1]) return solution(i-1,j,0); return solution(i-1,j,1); } if (j==1 && dp[i-1][1][1]!=0) return true; if (dp[i-1][j-1][0] > dp[i-1][j-1][1]) { if (dp[i-1][j-1][0] == dp[i-1][j][1]) return false; if (dp[i-1][j-1][0]> dp[i-1][j][1]) return solution(i-1,j-1,0); return solution(i-1,j,1); } if (dp[i-1][j-1][0] == dp[i-1][j-1][1] && dp[i-1][j-1][1]>=dp[i-1][j][1]) return false; if (dp[i-1][j-1][1] == dp[i-1][j][1]) return false; if (dp[i-1][j-1][1] > dp[i-1][j][1]) return solution(i-1,j-1,1); return solution(i-1,j,1); } main () { int n,m; while (1) { scanf ("%d%d",&n,&m); if (n+m==0) break; init(n,m); solve(n,m); if (solution(n+1,m,0)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator