| ||||||||||
| 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