区间型DP|【NOIP2007提高组】矩阵取数游戏
题目背景
NOIP2007提高组试题3。
题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n*m 的矩阵，矩阵中的每个元素 aij 均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共 n 个。m 次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分=被取走的元素值*2i ，其中 i 表示第 i 次取数（从1开始编号）；
4.游戏结束总得分为 m 次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入格式
输入文件game.in包括 n+1 行：
第1行为两个用空格隔开的整数 n 和 m 。
第 2～n+1 行为 n*m 矩阵，其中每行有 m 个用单个空格隔开的非负整数。
输出格式
输出文件仅包含 1 行，为一个整数，即输入矩阵取数后的最大得分。
样例数据 1
输入
2 3输出
1 2 3
3 4 2
82样例数据 2
输入
1 4输出
4 5 0 5
122样例数据 3
输入
2 10输出
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67
316994备注
【区间型DP|【NOIP2007提高组】矩阵取数游戏】【数据范围】
60% 的数据满足：1<=m,n<=30 ,答案不超过 1016
100% 的数据满足：1<=m,n<=80 , 0<=aij<=1000
【样例1说明】
第 1 次：第 1 行取行首元素，第 2 行取行尾元素，本次得分为 1*21+2*21=6
第 2 次：两行均取行首元素，本次得分为 2*22+3*22=20
第 3 次：得分为 3*23+4*23=56。总得分为 6+20+56+82
解析：
首先要观察到每一行是互不影响的（这非常重要！！）
然后就可以分开处理了。我们反着来考虑，令
文章图片
表示加到左端点为
文章图片
右端点为
文章图片
的最大得分就行了。
由于我太懒只写了60分的，再贴一个别人的100分高精度吧。。。
代码（60分）：
#include
using namespace std;
const int Max=35;
int n,m;
long long ans,f[Max][Max],num[Max][Max],Pow[Max];
inline long long solve(int i,int l,int r,int x)
{
if(f[l][r]) return f[l][r];
if(l==r) return num[i][l]*Pow[m];
f[l][r]=max(f[l][r],max(solve(i,l+1,r,x+1)+num[i][l]*Pow[x],solve(i,l,r-1,x+1)+num[i][r]*Pow[x]));
return f[l][r];
}int main()
{
scanf("%d%d",&n,&m),Pow[0]=1;
for(int i=1;
i<=30;
i++) Pow[i]=Pow[i-1]*2;
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++) cin>>num[i][j];
for(int i=1;
i<=n;
i++)
{
memset(f,0,sizeof(f));
ans+=solve(i,1,m,1);
}
cout< 代码（100分）：
#include
#include
#include
#include
#include
using namespace std;
const int maxnum = 35;
const int M = 100000000;
typedef unsigned long long ll;
int n, m, map[81][81];
struct highNum
{
ll num[maxnum];
highNum(int length = 1)
{
memset(num, 0, sizeof(num));
num[0] = length;
}
highNum operator = (highNum b)
{
memcpy(num, b.num, sizeof(b.num));
return *this;
}
highNum operator = (int b)
{
*this = highNum();
num[num[0]] = b;
return *this;
}
bool operator < (const highNum& b) const
{
if(num[0] < b.num[0]) return true;
if(num[0] == b.num[0])
{
for(int i = num[0];
i >= 1;
--i)
{
if(num[i] > b.num[i]) return false;
if(num[i] < b.num[i]) return true;
}
}
return false;
}
highNum operator + (const highNum& b) const
{
highNum c = highNum(max(num[0], b.num[0]));
for(int i = 1;
i <= c.num[0];
++i)
{
c.num[i] += num[i] + b.num[i];
c.num[i + 1] += c.num[i] / M;
c.num[i] %= M;
}
while(c.num[c.num[0] + 1] > 0)
{
++c.num[0];
c.num[c.num[0] + 1] += c.num[c.num[0]] / M;
c.num[c.num[0]] %= M;
}
return c;
}
highNum operator * (const int b) const
{
highNum c = highNum(num[0]);
for(int i = 1;
i <= c.num[0];
++i)
{
c.num[i] += num[i] * b;
c.num[i + 1] += c.num[i] / M;
c.num[i] %= M;
}
while(c.num[c.num[0] + 1] > 0)
{
++c.num[0];
c.num[c.num[0] + 1] += c.num[c.num[0]] / M;
c.num[c.num[0]] %= M;
}
while(c.num[c.num[0]] == 0 && c.num[0] > 1) --c.num[0];
return c;
}
highNum operator * (const highNum& b) const
{
highNum c = highNum(num[0] + b.num[0]);
for(int i = 1;
i <= num[0];
++i) for(int j = 1;
j <= b.num[0];
++j)
{
c.num[i + j - 1] += num[i] * b.num[j];
c.num[i + j] += c.num[i + j - 1] / M;
c.num[i + j - 1] %= M;
}
while(c.num[c.num[0] + 1] > 0)
{
++c.num[0];
c.num[c.num[0] + 1] += c.num[c.num[0]] / M;
c.num[c.num[0]] %= M;
}
while(c.num[c.num[0]] == 0 && c.num[0] > 1) --c.num[0];
return c;
}
};
ostream& operator << (ostream& o, highNum& b)
{
o << b.num[b.num[0]];
o.setf(ios::fixed);
o.width(8);
o.fill('0');
for(int i = b.num[0] - 1;
i >= 1;
--i) o << b.num[i];
return o;
}
highNum ans, f[81][81], pw[81];
void init()
{
cin >> n >> m;
for(int i = 1;
i <= n;
++i) for(int j = 1;
j <= m;
++j)
cin >> map[i][j];
pw[1] = 2;
for(int i = 2;
i <= m;
++i) pw[i] = pw[i - 1] * 2;
}
void work(int row)
{
for(int i = 1;
i <= m;
++i) for(int j = 1;
j <= m;
++j)
f[i][j] = highNum();
for(int i = 1;
i <= m;
++i) f[i][i] = pw[m] * map[row][i];
for(int p = 1;
p < m;
++p) for(int i = 1;
i <= m - p;
++i)
{
int j = i + p;
f[i][j] = max(f[i + 1][j] + pw[m - p] * map[row][i], f[i][j - 1] + pw[m - p] * map[row][j]);
}
ans = ans + f[1][m];
}
int main()
{
init();
for(int i = 1;
i <= n;
++i) work(i);
cout << ans;
return 0;
} 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长