poj 1157 LITTLE SHOP OF FLOWERS dp

几个月没碰过算法，现在完全不会了。

再过几周就要考试了，抓紧时间恢复一下

这是个简单dp，之前一直以不会dp为借口躲避这些题目，其实就是太懒了不想想。但是逃避总是逃不过的，于是恢复训练就从dp开始

注意这题每个花都必须要取到，之前这一点错了很多次

简单可以写出这样的dp代码

</pre><pre name="code" class="cpp">#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int org[105][105];
int dp[105][105];
int main()
{
    //freopen("1.txt","r",stdin);
    while(~scanf("%d%d",&F,&V))
    {
        int i,j;
        memset(org,0,sizeof(org));
        memset(dp,0,sizeof(dp));
        for(i=1;i<=F;i++)
            for(j=1;j<=V;j++)
            {
                scanf("%d",&org[i][j]);
            }
        dp[1][0]=org[1][1];
        for(i=1;i<=F;i++){
            for(j=i;j<=V;j++){
                dp[i][j]=org[i][j]+dp[i-1][j-1];
                if(j!=i)dp[i][j]=max(dp[i][j-1],dp[i][j]);
            }
        }
        printf("%d\n",dp[F][V]);
    }
}

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int org[105][105];
int dp[2][105];
int main()
{
	//freopen("1.txt","r",stdin);
	while(~scanf("%d%d",&F,&V))
	{
		int i,j;
		memset(org,0,sizeof(org));
		memset(dp,0,sizeof(dp));
		for(i=1;i<=F;i++)
			for(j=1;j<=V;j++)
			{
				scanf("%d",&org[i][j]);
			}
		dp[0][0]=org[1][1];
		bool flag=0;
		for(i=1;i<=F;i++){
			for(j=i;j<=V;j++){
				dp[flag][j]=org[i][j]+dp[!flag][j-1];
				if(j!=i)dp[flag][j]=max(dp[flag][j-1],dp[flag][j]);
			}
			flag=!flag;
		}
		printf("%d\n",dp[!flag][V]);
	}
}

到此为止?显然不。两次循环明显可以合并

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int dp[2][105];
int main()
{
	//freopen("1.txt","r",stdin);
	while(~scanf("%d%d",&F,&V))
	{
		int i,j;
		memset(dp,0,sizeof(dp));
		bool flag=0;
		int t;
		for(i=1;i<=F;i++){
			for(j=1;j<=V;j++){
				scanf("%d",&t);
				dp[flag][j]=t+dp[!flag][j-1];
				if(j>i)dp[flag][j]=max(dp[flag][j-1],dp[flag][j]);
			}
			flag=!flag;
		}
		printf("%d\n",dp[!flag][V]);
	}
}

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int F,V;
int dp[105];
int main()
{
	//freopen("1.txt","r",stdin);
	while(~scanf("%d%d",&F,&V))
	{
		int i,j,t,last,now;
		memset(dp,0,sizeof(dp));
		for(i=1;i<=F;i++){
			for(j=1;j<=V;j++){
				scanf("%d",&t);
				now=t+dp[j-1];
				if(j>i)now=max(last,now);
				dp[j-1]=last;last=now;
			}
		}
		printf("%d\n",now);
	}
}