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