題目描述
帥帥經常跟同學玩一個矩陣取數遊戲:對于一個給定的n*m的矩陣,矩陣中的每個元素aij均為非負整數。遊戲規則如下:
- 每次取數時須從每行各取走一個元素,共n個。m次後取完矩陣所有元素;
- 每次取走的各個元素隻能是該元素所在行的行首或行尾;
- 每次取數都有一個得分值,為每行取數的得分之和,每行取數的得分 = 被取走的元素值*2^i,其中i表示第i次取數(從1開始編号);
- 遊戲結束總得分為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[i−1][j]+num[i]∗2i+m−j+1,f[i][j+1]+num[j]∗2i+m−j+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 201
using namespace std;
struct num{
int s[maxn+];
inline num operator +(num b){
num c = {};int v = ;
for (int i = maxn; i > ; 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 = {}; int v = ;
for (int i = maxn; i > ; i --){
for (int j = maxn; j > ; j --){
c.s[maxn - ((maxn - i + ) + (maxn - j + ) - ) + ] += s[i] * b.s[j];
}
}
for (int i = maxn; i > ; i --){
if (c.s[i] >= mod){
c.s[i - ] += c.s[i] / mod;
c.s[i] = c.s[i] % mod;
}
}
return c;
}
inline num operator /(int x){
num c = {}; int v = ;
for (int i = ; 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 = {}; int v = ;
for (int i = maxn; i > ; i --){
if (s[i] - v >= b.s[i]){
c.s[i] = s[i] - b.s[i] - v, v = ;
}else{
c.s[i] = s[i] - b.s[i] - v + mod, v = ;
}
}
return c;
}
inline void read(int x){
int cnt = ;
do{
s[maxn - cnt++] = x % mod;
x /= mod;
}while (cnt <= maxn);
}
inline void output(){
int i = ;
num tmp = *this;
while (!tmp.s[i] && i < maxn){
i ++;
}
printf("%d", tmp.s[i]);
for (int j = i + ; j <= maxn; j ++){
int p = , f[];
fill(f, );
do{
f[p --] = tmp.s[j] % ;
}while (tmp.s[j] /= );
for (int k = ; k <= ; k++){
printf("%d",f[k]);
}
}
printf("\n");
}
}map[N][N], f[N][N], p[N];
inline int read(){
int x = , v = ;
char ch = getchar();
while (ch < '0' || ch > '9'){
if (ch == '-'){
v = -;
}
ch = getchar();
}
while (ch <= '9' && ch >= '0'){
x = x * + ch - '0';
ch = getchar();
}
return x * v;
}
inline num max(num x, num y){
int i = ;
while (!x.s[i] && i < maxn){
i ++;
}
int j = ;
while (!y.s[j] && j < maxn){
j ++;
}
int lenx = maxn - i + , leny = maxn - j + ;
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();
p[].read();
rep(i, , ){
p[i] = p[i - ] * two;
}
int n = read(), m = read();
rep(i, , n){
rep(j, , m){
map[i][j].read(read());
}
}
num prt;
fill(prt.s, );
rep(k, , n){
rep(i, , m){
drp(j, m + , i + ){
fill(f[i][j].s, );
int term = i + m - j + ;
if (i != ){
f[i][j] = map[k][i] * p[term] + f[i - ][j];
}
if (j != m + ){
f[i][j] = max(f[i][j], map[k][j] * p[term] + f[i][j + ]);
}
}
}
num ans;
fill(ans.s, );
rep(i, , m){
ans = max(ans, f[i][i + ]);
}
// ans.output();
prt = prt + ans;
}
prt.output();
return ;
}