JDOJ-1632: [NOIP2007]矩阵取数游戏 T3 高精度DP

[文章目录]

Description

帅帅经常更同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij据为非负整数。游戏规则如下:
1. 每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有的元素;
2. 每次取走的各个元素只能是该元素所在行的行首或行尾;
3. 每次取数都有一个得分值,为每行取数的得分之和;每行取数的得分 = 被取走的元素值*2^i,其中i表示第i次取数(从1开始编号);
4. 游戏结束总得分为m次取数得分之和。

帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

简单的想到DP,由于状态一定是连续的一段区间,并且行与行之间没有影响,所以记录端点DP。

dp[i][j]=max(dp[i-1][j]+a[i-1]*bin[k],bin[i][j+1]+a[j+1]*bin[k])。k为取的顺序中的第几个。然后一看数据,尼玛,高精度(不过nm^2的算法不整高精度也是可惜了)

然后写了个高精度,开心。额,我在练习自定义运算符啊。。。真的。。。

加了很清真的output(){非常方便调试}和maxx(node)函数。开心 代码好像不丑了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[100],mod=100000;
struct node
{
    int a[12];
    int len;
    node(){memset(a,0,sizeof(a));len=1;}
    node operator + (node x)
    {
        node ret;
        ret.len=max(len,x.len);
        int t=0;
        for(int i=1;i<=ret.len;i++)
        {
            ret.a[i]=(a[i]+x.a[i]+t)%mod;
            t=(a[i]+x.a[i]+t)/mod;
        }
        while(t) ret.a[++ret.len]=t%mod,t/=mod;
        return ret;
    }
    node operator *(int x)
    {
        node ret;
        if(x==0) return ret;
        ret.len=len;
        int t=0;
        for(int i=1;i<=len;i++)
        {
            ret.a[i]=(a[i]*x+t)%mod;
            t=(a[i]*x+t)/mod;
        }
        while(t) ret.a[++ret.len]=t%mod,t/=mod;
        return ret;//第一遍居然忘写了。玛丽有只小羊羔。。。有点小
    }
    node operator += (node x)
    {
        *this=*this+x;
        return *this;
    }
    void maxx(node x)
    {
        if(x.len!=len){if(x.len>len) *this=x; return ;}
        for(int i=len;i>0;i--)
            if(x.a[i]!=a[i]){if(x.a[i]>a[i]) *this=x; return ;}
        return ;
    }
    void output()
    {
        printf("%d",a[len]);
        for(int i=len-1;i>0/* 不能直接放个 i ,因为有len-1<0的情况,或者改写初始化就好了*/;i--) printf("%05d",a[i]);
        return ;
    }
}dp[100][100],ans,sum,bin[90],empty;
int main()
{
    cin>>n>>m;
    bin[0].a[1]=1;
    for(int i=1;i<=m;i++)
        bin[i]=bin[i-1]*2;
    while(n--)
    {
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        for(int i=m-1;i;i--)
        {
            for(int l=1,r;l+i-1<=m;l++)
            {
                r=l+i-1;
                dp[l][r]=empty;//初始化,嗯,长知识了。
                if(l-1>=1) dp[l][r].maxx(dp[l-1][r]+bin[m-i]*a[l-1]);
                if(r+1<=m) dp[l][r].maxx(dp[l][r+1]+bin[m-i]*a[r+1]);
            }
        }
        ans=empty;//ans=node();虽然是初始化了,但是相当于重新开了一个结构体,MLE 啊 
        for(int i=1;i<=m;i++)
            ans.maxx(dp[i][i]+bin[m]*a[i]);
        sum+=ans;
    }
    sum.output();
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注