NOIP2007矩阵取数[DP|高精度]
2024-08-29 03:44:31
题目描述
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的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行,为一个整数,即输入矩阵取数后的最大得分。
输入输出样例
输入样例#1:
2 3
1 2 3
3 4 2
输出样例#1:
82
说明
NOIP 2007 提高第三题
-------------------------------------
DP
行与行之间相互独立,各行单独求解;一定先清空
f(i,j)左选了i个,右选了j个的最大得分
状态转移很好想,注意边界处理
高精度[这次从数组1开始]
高加高,高乘低
输出时一定小心0
建议先写出long long 的方便调试
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
const int B=1e4,L=; struct big{
int size,d[L];
big(int a=):size(a){memset(d,,sizeof(int)*L);}
}; void jia(big &a,big &b){
int g=,i;
for(i=;;i++){
if(g==&&i>a.size&&i>b.size) break;
int tmp=g;
if(i<=a.size) tmp+=a.d[i];
if(i<=b.size) tmp+=b.d[i];
a.d[i]=tmp%B;
g=tmp/B;
}
a.size=i-;
} void chengInt(big &a,int k){
int g=,i;
for(i=;i<=a.size;i++){
int tmp=a.d[i]*k;
a.d[i]=(tmp+g)%B;
g=(tmp+g)/B;
}
while(g){
a.d[++a.size]=g%B;
g/=B;
}
} void copy(big &t,big &s){
t.size=s.size;
for(int i=;i<=s.size;i++) t.d[i]=s.d[i];
} big max(big &a,big &b){
if(a.size>b.size) return a;
if(a.size<b.size) return b;
for(int i=a.size;i>=;i--){
if(a.d[i]>b.d[i]) return a;
if(a.d[i]<b.d[i]) return b;
}
return a;
} void print(big &a){
for(int i=a.size;i>=;i--){
if(i==a.size);
else if(a.d[i]<) cout<<"";
else if(a.d[i]<) cout<<"";
else if(a.d[i]<) cout<<"";
cout<<a.d[i];
}
cout<<"\n";
} int n,m;
int a[N][N];
big f[N][N];
big ans,fin=; big two[N];
void PRE(){
two[].d[]=;
for(int i=;i<=m+;i++){
copy(two[i],two[i-]);
chengInt(two[i],);
}
}
big sol(int num){
ans=big();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) f[i][j]=big(); f[][].d[]=a[num][]*;
f[][].d[]=a[num][m]*;
for(int i=;i<=m;i++){
// f[i][0]=f[i-1][0]+a[num][i]*((ll)1<<i);
// f[0][i]=f[0][i-1]+a[num][m-i+1]*((ll)1<<i); copy(f[i][],f[i-][]);
big tmp; copy(tmp,two[i]); chengInt(tmp,a[num][i]);
jia(f[i][],tmp); copy(f[][i],f[][i-]);
big tmp2; copy(tmp2,two[i]); chengInt(tmp2,a[num][m-i+]);
jia(f[][i],tmp2); }
for(int i=;i<=m;i++)
for(int j=;j<=m-i;j++){
// f[i][j]=max(f[i-1][j]+a[num][i]*((ll)1<<(i+j)),
// f[i][j-1]+a[num][m-j+1]*((ll)1<<(i+j))); big x,y;
copy(x,f[i-][j]);
big tmp; copy(tmp,two[i+j]); chengInt(tmp,a[num][i]);
jia(x,tmp); copy(y,f[i][j-]);
big tmp2; copy(tmp2,two[i+j]); chengInt(tmp2,a[num][m-j+]);
jia(y,tmp2); f[i][j]=max(x,y);
} for(int i=;i<=m;i++) ans=max(ans,f[i][m-i]);
return ans;
} int main(){//system("pause");
cin>>n>>m;
PRE();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>a[i][j]; for(int i=;i<=n;i++) {big tmp=sol(i);jia(fin,tmp);}
print(fin); }
最新文章
- Tesseract API在VS 2013中的配置以及调用
- 配置RAC到单节点standby的data guard
- css3 keyframes在yuicompressor下压缩问题
- php判断爬虫
- RC-50221 问题解决 - netstat 查看端口占用情况
- Python还是很重要的,不能丢。学习IF和WHILE
- [Immutable.js] Exploring Sequences and Range() in Immutable.js
- 一位资深程序员给予Java初学者的学习路线建议
- YARN笔记——技术点汇总
- DB Query Analyzer 6.04 is distributed, 78 articles concerned have been published
- RecyclerView 刷新后自动滚动的问题,notifyDataSetChanged 后自己滚动
- IDEA打包jar包
- PropTypes使用
- MySQL——SQL Mode详解
- HihoCoder - 1336 二维数状数组(单点更新 区间查询)
- Css常用属性单位
- 数据分析sql常用整理
- 微软智能云的核心DNA
- Error Note1:错误修复笔记
- 51nod 1276 1276 岛屿的数量 (很好玩的题目