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

那位大哥帮看看,WA得不行了

Posted by asdqwe at 2006-08-05 00:05:09 on Problem 2889
#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:
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