poj-3661-另一种做法（滚动数组）

题意：上一篇博客~~

做法：

根据上一篇博客我们知道，dp[i][0]的值与dp[i-k][k]的最大值有关系。

dp[i][j]只与dp[i-1][j-1]有关系。

那么我们就建立一个数组fan[x]，fan[x]代表到现在的i为止，dp[i-k][k]的最大值（i-k+k=x）。

每执行一分钟，就更新一次数组fan[x]。

两个做法的结果比较：

第一种做法，二维数组：

第二种做法，滚动数组：

我们可以发现用时差不多，但是数组小了很多，所以说当n比较大的时候，可以选择用第二种做法。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INF_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int main()
{int n,m,i,j;int d[10001];scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d",&d[i]);}int dp[2][501];int fan[10001];memset(fan,0,sizeof(fan));for(j=0;j<=m;j++)dp[0][j]=0;for(i=1;i<=n;i++){dp[i%2][0]=max(fan[i],dp[(i-1)%2][0]);dp[i%2][1]=dp[(i-1)%2][0]+d[i];for(j=2;j<=m;j++){if(dp[(i-1)%2][j-1]!=0)dp[i%2][j]=dp[(i-1)%2][j-1]+d[i];else dp[i%2][j]=0;}for(j=1;j<=m;j++){if(i+j<=n&&dp[i%2][j])fan[i+j]=max(fan[i+j],dp[i%2][j]);}}printf("%d\n",dp[n%2][0]);return 0;
}