NOIP2007複賽提高組 矩陣取數遊戲 解題報告

3、矩陣取數遊戲 （game.pas/c/cpp）

【問題描述】

帥帥經常更同學玩一個矩陣取數遊戲：對於一個給定的n*m的矩陣，矩陣中的每個元素aij據爲非負整數。遊戲規則如下：

1. 每次取數時須從每行各取走一個元素，共n個。m次後取完矩陣所有的元素；

2. 每次取走的各個元素只能是該元素所在行的行首或行尾；

3. 每次取數都有一個得分值，爲每行取數的得分之和；每行取數的得分 = 被取走的元素值*2i，其中i表示第i次取數（從1開始編號）；

4. 遊戲結束總得分爲m次取數得分之和。

帥帥想請你幫忙寫一個程序，對於任意矩陣，可以求出取數後的最大得分。

【輸入】

輸入文件game.in包括n+1行；

第一行爲兩個用空格隔開的整數n和m。

第2~n+1行爲n*m矩陣，其中每行有m個用單個空格隔開

【輸出】

輸出文件game.out僅包含1行，爲一個整數，即輸入矩陣取數後的最大的分。

【輸入輸出樣例1】

game.in	game.out
2 3 1 2 4 3 4 2	82

【輸入輸出樣例1解釋】

第1次：第一行取行首元素，第二行取行尾元素，本次的分為1*21+2*21=6

第2次：兩行均取行首元素，本次得分爲2*22+3*22=20

第3次：得分爲3*23+4*23=56。總得分爲6+20+56=82

【輸入輸出樣例2】

game.in	game.out
1 4 4 5 0 5	122

【輸入輸出樣例3】

game.in	game.out
2 10 96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67	316994

【限制】

60%的數據滿足：1<=n, m<=30，答案不超過1016

100%的數據滿足：1<=n, m<=80，0<=aij<=1000

【分析】
(http://www.byvoid.com/blog/noip-allsolutions/)

動態規劃。由於每行是互不影響的，可以把每行孤立開看，對每行分別進行一次動態規劃計算。結果可能很大，需要高精度計算。爲避免計算高精度乘法，可以在初始化時把每個數的2^k遞推算出。

狀態設定

F[i,j] 爲當前行取前i個數和後j個數的最大得分。

V[i,j] 爲當前行第i個數乘以2^j的值。

狀態轉移方程

F[i,j]=max{ F[i-1,j] + V[i,p] , F[i,j-1] + V[M-j+1,p] } p=i+j(表示當前是第幾次取數)

V[i,j]=V[i,j-1]+V[i,j-1]

邊界條件

V[i,1]=當前行第i個數的值

F[0,0]=0

每行結果

Max{ F[i,M-i] } (0<=i<=M)

最終結果

每行結果的總和

【代碼】
由於數據很強，在我的電腦上的評測結果是：超時2組。

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int SIZE=50;
class hugeint
{
public:
    unsigned int len;
    unsigned int num[SIZE];
    hugeint()
    {
        len=0;
        memset(num,0,sizeof(num));
    }
};

hugeint V[82][82];//V[i,j]為當前行第i個數乘以2^j的積
hugeint A[82];//A為讀入的矩陣的每一行
hugeint F[82][82];//F[i,j]為當前行取前i個數和後j個數的最大得分
hugeint tsum;
hugeint Two;
int N,M;//行數,列數

hugeint times(hugeint a,hugeint b)
{
    unsigned  int i,j;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    for (i=1;i<=a.len;i++)
        for (j=1;j<=b.len;j++)
            ans.num[i+j-1]+=a.num[i]*b.num[j];
    for (i=1;i<=a.len+b.len;i++)
    {
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]=ans.num[i]%10;
    }
    if (ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;
    return ans;
}

hugeint add(hugeint a,hugeint b)
{
    unsigned int i;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    if (a.len>b.len)
        ans.len=a.len;
    else
        ans.len=b.len;
    for (i=1;i<=ans.len;i++)
    {
        ans.num[i]+=(a.num[i]+b.num[i]);
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
    }
    if (ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

hugeint average(hugeint a,hugeint b)
{
    int i;
    hugeint ans;
    ans=add(a,b);
    for (i=ans.len;i>=2;i--)
    {
        ans.num[i-1]+=(ans.num[i]%2)*10;
        ans.num[i]/=2;
    }
    ans.num[i]/=2;
    if (ans.num[ans.len]==0)
        ans.len--;
    return ans;
}

bool over(hugeint a,hugeint b)
{
    int i;
    if (a.len<b.len)
        return false;
    if (a.len>b.len)
        return true;
    for (i=a.len;i>=1;i--)
    {
        if (a.num[i]<b.num[i])
            return false;
        if (a.num[i]>b.num[i])
            return true;
    }
    return false;
}

void PreDP()
{
    for (int i=1;i<=M;i++)
        V[i][0]=A[i];
    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=M;j++)
            V[i][j]=times(Two,V[i][j-1]);
    }
}

hugeint DP()
{
    hugeint sum;
    int p;
    for (int i=0;i<=M;i++)
    {
        for (int j=0;j<=M;j++)
        {
            hugeint m;
            p=i+j;
            if(p>M)
                continue;
            if (i-1>=0)  
            {
                if ( over( add(F[i-1][j],V[i][p]),m     )  )
                    m=add(F[i-1][j],V[i][p]);
            }
            if (j-1>=0)
            {
                if ( over( add(F[i][j-1],V[M-j+1][p]),m )  )
                    m=add(F[i][j-1],V[M-j+1][p]);
            }
            F[i][j]=m;
        }
    }
    for (int i=0;i<=M;i++)
    {
        if(  over(F[i][M-i],sum)  )
            sum=F[i][M-i];
    }
    return sum;
}

void init()
{
    Two.len=1;
    Two.num[1]=2;
    cin>>N>>M;
    char word[10]={'\0'};
    hugeint target;
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            memset(word,'\0',sizeof(word));
            cin>>word;
            memset(target.num,0,sizeof(target.num));
            target.len=strlen(word);
            for (unsigned int k=1;k<=target.len;k++)
                target.num[k]=word[target.len-k]-'0';
            A[j]=target;
        }
        PreDP();
        tsum=add(tsum,DP());
    }
}

int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    init();
    for (int i=tsum.len;i>=1;i--)
        cout<<tsum.num[i];
    return 0;
}