矩阵取数游戏_洛谷1005_高精度dp

2017-01-14 19:44:19来源:CSDN作者:jpwang8人点击

第七城市

题目描述


帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:

  1. 每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;

  2. 每次取走的各个元素只能是该元素所在行的行首或行尾;

  3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值*2^i,其中i表示第i次取数(从1开始编号);

  4. 游戏结束总得分为m次取数得分之和。

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

输入格式:


输入文件game.in包括n+1行:

第1行为两个用空格隔开的整数n和m。

第2~n+1行为n*m矩阵,其中每行有m个用单个空格隔开的非负整数。

数据范围:


60%的数据满足:1<=n, m<=30,答案不超过10^16

100%的数据满足:1<=n, m<=80,0<=aij<=1000

输出格式:


输出文件game.out仅包含1行,为一个整数,即输入矩阵取数后的最大得分。

Analysis


本来一道很水的dp被硬生生加上高精度,调wa到想死(哭泣
首先可以想到这些行之间是没有关系影响的,那么完全可以边读边做,就变成一段序列两边取数字求最大值
两种思路,从两边往中间取,那么f[i][j]表示从前往后取了i个数字,从后往前取了j个数字,
方程 f[i][j]=max{f[i1][j]+num[i]2i+mj+1,f[i][j+1]+num[j]2i+mj+1}
特别的,我们规定f[0][m]只能往后取,f[1][m+1]只能往前取
2的n次方可以打表,高精度压位会比较快

从中间取大概就是每加上一个数字就把转移前的状态*2,不用考虑乘方,不会写
除了高精度基本没难度的题

Code


#include <stdio.h>#include <string.h>#define rep(i, a, b) for (int i = a; i <= b; i ++)#define drp(i, a, b) for (int i = a; i >= b; i --)#define fill(x, t) memset(x, t, sizeof(x))#define maxn 10#define mod 10000#define N 201using namespace std;struct num{    int s[maxn+1];    inline num operator +(num b){        num c = {0};int v = 0;        for (int i = maxn; i > 0; i --){            c.s[i] = (s[i] + b.s[i] + v) % mod;            v = (s[i] + b.s[i] + v) / mod;        }        return c;    }    inline num operator *(num b){        num c = {0}; int v = 0;        for (int i = maxn; i > 0; i --){            for (int j = maxn; j > 0; j --){                c.s[maxn - ((maxn - i + 1) + (maxn - j + 1) - 1) + 1] += s[i] * b.s[j];            }        }        for (int i = maxn; i > 0; i --){            if (c.s[i] >= mod){                c.s[i - 1] += c.s[i] / mod;                c.s[i] = c.s[i] % mod;            }        }        return c;    }    inline num operator /(int x){        num c = {0}; int v = 0;        for (int i = 1; i <= maxn; i ++){            int t = v * mod + s[i];            c.s[i] = t / x;            v = t % x;        }        return c;    }    inline num operator -(num b){        num c = {0}; int v = 0;        for (int i = maxn; i > 0; i --){            if (s[i] - v >= b.s[i]){                c.s[i] = s[i] - b.s[i] - v, v = 0;            }else{                c.s[i] = s[i] - b.s[i] - v + mod, v = 1;            }        }        return c;    }    inline void read(int x){        int cnt = 0;        do{            s[maxn - cnt++] = x % mod;            x /= mod;        }while (cnt <= maxn);    }    inline void output(){        int i = 0;        num tmp = *this;        while (!tmp.s[i] && i < maxn){            i ++;        }        printf("%d", tmp.s[i]);        for (int j = i + 1; j <= maxn; j ++){            int p = 4, f[5];            fill(f, 0);            do{                f[p --] = tmp.s[j] % 10;            }while (tmp.s[j] /= 10);            for (int k = 1; k <= 4; k++){                printf("%d",f[k]);            }        }        printf("/n");    }}map[N][N], f[N][N], p[N];inline int read(){    int x = 0, v = 1;    char ch = getchar();    while (ch < '0' || ch > '9'){        if (ch == '-'){            v = -1;        }        ch = getchar();    }    while (ch <= '9' && ch >= '0'){        x = x * 10 + ch - '0';        ch = getchar();    }    return x * v;}inline num max(num x, num y){    int i = 0;    while (!x.s[i] && i < maxn){        i ++;    }    int j = 0;    while (!y.s[j] && j < maxn){        j ++;    }    int lenx = maxn - i + 1, leny = maxn - j + 1;    if (lenx < leny){        return y;    }else if (lenx > leny){        return x;    }else{        while (i <= maxn && j <= maxn){            if (x.s[i] > y.s[j]){                return x;            }else if (x.s[i] < y.s[j]){                return y;            }            i ++;            j ++;        }    }    return x;}int main(void){    num two;    two.read(2);    p[0].read(1);    rep(i, 1, 81){        p[i] = p[i - 1] * two;    }    int n = read(), m = read();    rep(i, 1, n){        rep(j, 1, m){            map[i][j].read(read());        }    }    num prt;    fill(prt.s, 0);    rep(k, 1, n){        rep(i, 0, m){            drp(j, m + 1, i + 1){                fill(f[i][j].s, 0);                int term = i + m - j + 1;                if (i != 0){                    f[i][j] = map[k][i] * p[term] + f[i - 1][j];                }                if (j != m + 1){                    f[i][j] = max(f[i][j], map[k][j] * p[term] + f[i][j + 1]);                }            }        }        num ans;        fill(ans.s, 0);        rep(i, 0, m){            ans = max(ans, f[i][i + 1]);        }        // ans.output();        prt = prt + ans;    }    prt.output();    return 0;}
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台