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)を表す.
実行1分ごとに配列fan[x]が更新される.
2つの方法の結果を比較します.
1つ目の方法は、2 D配列です.
 
19828K
172MS
 
 
2つ目の方法は、配列をスクロールすることです.
 
248K
188MS
 
 
時差ぼけは多くないが,配列はかなり小さいことが分かったので,nが大きい場合には第2の方法を選ぶことができると述べた.
 

#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
",dp[n%2][0]);

    return 0;

}