[動態規劃][貪心策略]OI練習題：多重數列 linesum

         多重數列（linesum.cpp/pas/c）

給出n個長度爲m的數字序列S1,S2..Sn，找出一個子序列S',使得S'的各項和最大，

且S'中的相鄰兩個元素在原串中的位置差必須是2^k+1(k>0)，

比如說，選取了第1個元素，下一個只能選取第4個，第6個，第10個…(距離相差2^1+1，2^2+1，2^3+1…)

如果選取了原串中第k個元素，則可以從S1[k]，S2[k]，S3[k]...Sn[k]中任選一個加入S'

輸入格式：

第一行有兩個整數n,m

第2到n+1行，每行有一個長度爲m的數字序列

輸出格式：

一行，最大的子序列和值

樣例輸入：

2 10

1 0 -1 3 2 1 -4 10 1 3

2 3 -2 -7 3 4 1 2 4 9

樣例輸出

16

（第2個序列的第2個，第5個和第一個序列的第8個）

數據規模：

對於30%的數據，m<=10000

對於100%的數據 m<=1000000,n<=5,答案不超過longint/int範圍

【分析】

變形很嚴重的背包問題！可以動態規劃出結果。

先初始化K數組，表示 2^k+1。

 int K[21]={0,3,5,9,17,33,65,129,257,513,1025,2049,4097,8193,

16385,32769,65537,131073,262145,524289};

讀入時需要貪心策略，使讀入完畢後 同一位置上的數最大.

例如樣例：

1 0 -1 3 2 1 -4 10 1 3

2 3 -2 -7 3 4 1 2 4 9，

讀入後僅有一行，為

2,3,-1,3,3,4,1,10,4,9。

把這個數組表示為a[],

然後動態規劃。

狀態設定

                 F[i]表示以a數組第i個數為S'第一個數的最大和

初始狀態 

                 F[i]=0(或者MIN) (0<=i<=M)

狀態轉移方程

                 F[i]=0  (i-k[1]<0)

                 F[i]=max{F[i],F[i-K[j]]+a[i]} (1<=j<=19)

目標狀態

                 max{F[i]}  (i<=i<=M)

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define Max(a,b) a>b?a:b
using namespace std;
const int MAXN=0xfffffff;
int S[1000001];
int K[21]=
{0,3,5,9,17,33,65,129,257,513,1025,2049,4097,8193,16385,32769,65537,131073,262145,524289};

int N,M;

void init()
{
    scanf("%d %d",&N,&M);
    for (int i=1;i<=M;i++)
        S[i]=0-MAXN;
    int Temp;
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            scanf("%d",&Temp);
            S[j]=Max(S[j],Temp);
        }
    }
}

int ans[1000001];
void DP()
{
    int Ans=0-MAXN;
    for (int i=1;i<=M;i++)
    {
        ans[i]=S[i];
        for(int j=1;j<=19;j++)
        {
            if(i-K[j]<0)
                break;
            ans[i]=Max(ans[i],ans[i-K[j]]+S[i]);
        }
        Ans=Max(Ans,ans[i]);
    }
    printf("%d\n",Ans);
}

int main()
{
    freopen("linesum.in","r",stdin);
    freopen("linesum.out","w",stdout);
    init();
    DP();
    return 0;
}