| 记录编号 |
461166 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOIP 2007]矩阵取数游戏 |
最终得分 |
100 |
| 用户昵称 |
 胡嘉兴 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.244 s |
| 提交时间 |
2017-10-19 10:15:50 |
内存使用 |
12.43 MiB |
显示代码纯文本
#include<algorithm>
#include<cstring>
#include<iostream>
#include<stack>
#include<cstdio>
#define LL long long
#define N 87
using namespace std;
const LL maxn=207;
int a[N][N];
typedef struct Bigint{
LL a[maxn];
void print(){//输出
for(LL i=a[0];i>=1;i--)
{
printf("%lld", a[i]);
}
puts("");
}
void Init(string s){//赋值
memset(a,0,sizeof(a));
a[0]=s.size();
for(LL i=1;i<=a[0];i++)a[i]=s[a[0]-i]-'0';
while(a[0]>1 && a[a[0]]==0)a[0]--;
}
void init(LL temp){
memset(a,0,sizeof(a));
a[0]=1;
a[1]=temp;
}
Bigint operator + (const Bigint & b)const{//高精加高精
Bigint c;memset(c.a,0,sizeof(c.a));
c.a[0]=max(a[0],b.a[0]);
for(LL i=1;i<=c.a[0];i++){
c.a[i]+=a[i]+b.a[i];
if(c.a[i]>9){
c.a[i+1]++;
c.a[i]-=10;
}
}
if(c.a[c.a[0]+1])c.a[0]++;
return c;
}
Bigint operator - (const Bigint & b)const{//高精减高精
Bigint c;memset(c.a,0,sizeof(c.a));
c.a[0]=max(a[0],b.a[0]);
for(LL i=1;i<=c.a[0];i++){
c.a[i]+=a[i]-b.a[i];
if(c.a[i]<0){
c.a[i+1]--;
c.a[i]+=10;
}
}
while(c.a[0]>1 && c.a[c.a[0]]==0)c.a[0]--;
return c;
}
Bigint operator * (const Bigint & b)const{//高精乘高精
Bigint c;
memset(c.a,0,sizeof(c.a));
c.a[0]=a[0]+b.a[0]-1;
for (int i = 1; i <= a[0]; i ++){
int tem = 0;
for (int j = 1; j <= b.a[0]; j ++){
tem = a[i] * b.a[j] + tem / 10 + c.a[i + j - 1] ;
c.a[i + j - 1] = tem % 10;
}
if (tem / 10){
c.a[i + b.a[0]] = tem / 10;
}
}
if(c.a[c.a[0]+1]){
c.a[0]++;
}
while(c.a[0]>1 && c.a[c.a[0]]==0){
c.a[0]--;
}
return c;
}
bool operator < (const Bigint & b)const{//重载小于号
if(a[0]<b.a[0])return true;
if(a[0]>b.a[0])return false;
for(LL i=a[0];i;i--){
if(a[i]>b.a[i])return false;
if(a[i]<b.a[i])return true;
}
return false;
}
bool operator == (const Bigint & b)const{//重载等于号
if(a[0]^b.a[0])return false;
for(LL i=a[0];i;i--)if(a[i]^b.a[i])return false;
return true;
}
bool operator > (const Bigint & b)const{//重载大于号
if(a[0]<b.a[0])return false;
if(a[0]>b.a[0])return true;
for(LL i=a[0];i;i--){
if(a[i]>b.a[i])return true;
if(a[i]<b.a[i])return false;
}
return false;
}
Bigint operator / (const LL & temp)const{//高精除低精
Bigint b; memset(b.a,0,sizeof(b.a));
b.a[0]=a[0];
LL x=0;
for(LL i=a[0];i>=1;i--){
b.a[i]=(x*10+a[i])/temp;
x=(x*10+a[i])%temp;
}
while(b.a[0]>1 && b.a[b.a[0]]==0)b.a[0]--;
return b;
}
Bigint operator * (const LL & temp)const{//高精乘低精
Bigint b;memset(b.a,0,sizeof(b.a));
b.a[0]=a[0];
for(LL i=1;i<=a[0];i++)b.a[i]=a[i]*temp;
for(LL i=1;i<=b.a[0];i++){
if(b.a[i]>9){
b.a[i+1]+=b.a[i]/10;
b.a[i]%=10;
if(i==b.a[0])b.a[0]++;
}
}
while(b.a[0]>1 && b.a[b.a[0]]==0)b.a[0]--;
return b;
}
LL operator % (const LL & temp)const{//高精模低精
LL date=0;
for(LL i=a[0];i>=1;i--){
date=date*10+a[i];
date%=temp;
}
return date;
}
}BIG;
Bigint numcpy(const Bigint p,LL pos){//从pos开始的地方复制p数组到q数组
Bigint a;memset(a.a,0,sizeof(a.a));
for(LL i=1;i<=p.a[0];i++)a.a[i+pos-1]=p.a[i];
a.a[0]=p.a[0]+pos-1;
return a;
}
Bigint operator / (Bigint & a,Bigint & b){//高精除高精
Bigint c;memset(c.a,0,sizeof(c.a));
if(a==b){c.Init("1");return c;}
if(a<b){c.Init("0");return c;}
c.a[0]=a.a[0]-b.a[0]+1;
for(LL i=c.a[0];i>0;i--){
Bigint temp=numcpy(b,i);
while(a>temp || a==temp){c.a[i]++;a=a-temp;}
}
while(c.a[0]>1 && c.a[c.a[0]]==0)c.a[0]--;
return c;
}
Bigint operator % (Bigint & a,Bigint & b){//高精模高精
Bigint c;memset(c.a,0,sizeof(c.a));
if(a==b){c.Init("0");return c;}
if(a<b)return a;
c.a[0]=a.a[0]-b.a[0]+1;
for(LL i=c.a[0];i>0;i--){
Bigint temp=numcpy(b,i);
while(a>temp || a==temp){
c.a[i]++;
a=a-temp;
}
}
return a;
}
void f_print(BIG a)
{
for(int i = a.a[0]; i >= 1; i--)
{
printf("%d", a.a[i]);
if((a.a[0]-i+1)%70==0&&i!=1)
{
puts("");
}
}
puts("");
}
Bigint qpow(Bigint a,int k){//高精快速幂
Bigint ans;
ans.Init("1");
while(k){
if(k&1)
{
ans=ans*a;
}
a=a*a;
k>>=1;
}
return ans;
}
void BIG_sqrt()
{
BIG a,l,r,yi,ans;
string s;
cin>>s;
a.Init(s);
l.Init("0");
r.Init(s);
yi.Init("1");
while(l<r||l==r){
BIG mid=l+r;
mid=mid/2;
Bigint ans;
ans=mid*mid;
if(ans==a)
{
mid.print();
return;
}
if(ans<a)
{
l=mid+yi;
}
else
{
r=mid-yi;
}
}
r.print();
}
BIG f[N][N],anc[N];
void BEG(int n)
{
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
f[i][j].init(0);
}
}
return;
}
int main()
{
int n, m;
BIG ans;
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]);
}
}
anc[0].init(1);
for(int i = 1; i <= m; i++)
{
anc[i] = anc[i-1]*2;
}
for(int k = 1; k <= n; k++)
{
BIG maxk;
maxk.init(0);
BEG(m);
for(int i = 1; i <= m; i++)
{
for(int j = 0; j <= i; j++)
{
if(j == 0)
{
f[i][j] = f[i-1][j]+anc[i]*a[k][m-i+j+1];
if(i==m)
{
if(f[m][j]>maxk)
{
maxk = f[m][j];
}
}
continue;
}
if(i == j)
{
f[i][j] = f[i-1][j-1]+anc[i]*a[k][j];
if(i==m)
{
if(f[m][j]>maxk)
{
maxk = f[m][j];
}
}
continue;
}
BIG x = f[i-1][j]+anc[i]*a[k][m-i+j+1], y = f[i-1][j-1]+anc[i]*a[k][j];
if(x>y)
{
f[i][j] = x;
}
else
{
f[i][j] = y;
}
if(i==m)
{
if(f[m][j]>maxk)
{
maxk = f[m][j];
}
}
}
}
ans = ans + maxk;
}
ans.print();
return 0;
}