np馅饼有关问题

np馅饼问题

#include<iostream>
#define MAX(a,b) ((a)>(b)?(a):(b))

using namespace std;
#define M 10
#define T 10000
int s[T+1][M+1]={0};


int getmax(int s[T+1][M+1],int dp[T+1][M+1],int t){

int i,j;
for(j=0;j<=M;++j)
s[t][j]=0;
for(i=t-1;i>=0;--i)
for(j=0;j<=M;++j){
if(j==0){
s[i][j]=MAX((s[i+1][j]+dp[i+1][j]),(s[i+1][j+1]+dp[i+1][j+1]));}
else
if(j==10){
s[i][j]=MAX((s[i+1][j]+dp[i+1][j]),(s[i+1][j-1]+dp[i+1][j-1]));
}
else
s[i][j]=MAX((s[i+1][j]+dp[i+1][j]),MAX((s[i+1][j+1]+dp[i+1][j+1]),(s[i+1][j-1]+dp[i+1][j-1])));
}


return s[0][5];

}


int  main(){
int dp[T+1][M+1]={0};
int k;
int t;
//int m;
//cin>>m;
cin>>k;
int maxt=0;
while(k){
cin>>t;
if(t>maxt)
maxt=t;
dp[t][k]++;

cin>>k;
}
cout<<getmax(s,dp,maxt)<<endl;
return 0;
}

这是我写的代码，结果不对，是哪里错了呢？是s[i][j]表示从i秒j位置开始能得到的最多的馅饼。dp[i][j]表示isj位置出现的馅饼数，帮看看啊
[解决办法]
主要问题：
1. 数组不够大(见题目0<n<100000）
2. main中输入处理与getmax调用的逻辑错
3. s与dp两个数组不能协调

建议修改如下：

#include<iostream>
#define MAX(a,b) ((a)>(b)?(a):(b))

using namespace std;
#define M 10
//错#define T 10000
#define T 100000
//int s[T+1][M+1]={0};


//int getmax(int s[T+1][M+1],int dp[T+1][M+1],int t){
int getmax(int dp[T+1][M+1],int t){

  int i,j;
  //for(j=0;j<=M;++j)
  //  s[t][j]=0;
  for(i=t-1;i>=0;--i)
    for(j=0;j<=M;++j){
      if(j==0){
        //s[i][j]=MAX((s[i+1][j]+dp[i+1][j]),(s[i+1][j+1]+dp[i+1][j+1]));}
        dp[i][j]+=MAX(dp[i+1][j],dp[i+1][j+1]);}
      else
      if(j==10){
          //s[i][j]=MAX((s[i+1][j]+dp[i+1][j]),(s[i+1][j-1]+dp[i+1][j-1]));
          dp[i][j]+=MAX(dp[i+1][j],dp[i+1][j-1]);
        }
      else
        //s[i][j]=MAX((s[i+1][j]+dp[i+1][j]),MAX((s[i+1][j+1]+dp[i+1][j+1]),(s[i+1][j-1]+dp[i+1][j-1])));
        dp[i][j]+=MAX(dp[i+1][j],MAX(dp[i+1][j+1],dp[i+1][j-1]));
    }


return dp[0][5];//return s[0][5];

}


int  main(){
  static int dp[T+1][M+1]={0};//错int dp[T+1][M+1]={0};
  int k;
  int t;
  int m;
  int i;
  while (cin>>m && m) 
 
  {
    int maxt=0;
    memset(dp, 0, sizeof(dp));
    for (i = 0; i < m; i++)
    {
      cin>>k>>t;
      if(t>maxt)
        maxt=t;
      dp[t][k]++;
    }
    cout<<getmax(dp,maxt)<<endl;//cout<<getmax(s,dp,maxt)<<endl;
  }
  return 0;
}

查看更多 下一篇