pku(1157)LITTLE SHOP OF FLOWERS

作者在 2008-03-14 13:49:32 发布以下内容

动态规划:

  不要想当然的以为最小值就是0,(o(∩_∩)o...)我就是这么wa了一次。

 

代码:

 

 

#include <iostream>
using namespace std;
long sum[101]={0};
long tempsum[101]={0};
long bunch[101][101]={0};
long max(int i, int j)//求最大值
{

 long temp=-2147483648;
 for(int s=i;s<=j;s++)
 {
  if(sum[s]>temp)
   temp=sum[s];
 }
 return temp;
}
void build_summax(int i,int j)//动态规划核心部分
{
 tempsum[j]=max(i-1,j-1)+bunch[i][j];
}
void truesum(int V)//得SUM
{
 for(int j=0;j<V;j++)
  sum[j]=tempsum[j];
}
main()
{
 int F,V;
 cin >>F>>V;
 for(int i=0;i<F;i++)
  for(int j=0;j<V;j++)
   cin>>bunch[i][j];

  for(i=0;i<V;i++)//初始化第一行
  {
   sum[i]=bunch[0][i];
   tempsum[i]=bunch[0][i];
  }


  for(i=1;i<F;i++)//注意约束
  {
   for(int j=i;j<V;j++)
   build_summax(i,j);
  truesum(V);
  }
  cout<<max(F-1,V-1)<<endl;
  return 0;
}


 

acm | 阅读 2322 次
文章评论,共0条
游客请输入验证码
浏览255954次