Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

code

Posted by nuanran at 2006-08-02 09:51:52 on Problem 2889
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator