AC日记——矩阵取数游戏 洛谷 P1005

矩阵取数游戏

思路:

  dp+高精;

代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct Int {
int len;
char ai[];
Int()
{
len=,ai[]=;
}
void Count(int pos)
{
len++;
if(pos/) Count(pos/);
}
void operator=(int pos_)
{
int pos=pos_;
len=,Count(pos);
for(int i=;i<len;i++) ai[i]=pos%,pos/=;
}
bool operator<(const Int pos)const
{
if(len<pos.len) return true;
else if(len>pos.len) return false;
for(int i=len-;i>=;i--)
{
if(ai[i]<pos.ai[i]) return true;
else if(ai[i]>pos.ai[i]) return false;
}
return false;
}
Int operator*(const int pos)const
{
ll tmp=;Int res;res.len=len;
for(int i=;i<len;i++) tmp+=ai[i]*pos,res.ai[i]=tmp%,tmp/=;
while(tmp) res.ai[res.len++]=tmp%,tmp/=;
return res;
}
Int operator+(const Int pos)const
{
ll tmp=;Int res;res.len=max(len,pos.len);
for(int i=;i<res.len;i++) tmp+=(i<len?ai[i]:)+(i<pos.len?pos.ai[i]:),res.ai[i]=tmp%,tmp/=;
while(tmp) res.ai[res.len++]=tmp%,tmp/=;
return res;
}
void print()
{
for(int i=len-;i>=;i--) putchar(ai[i]+'');
}
};
Int dp[][],ans,ci[][];
int ai[][],n,m;
Int max(Int a,Int b)
{
if(a<b) return b;
else return a;
}
int main()
{
freopen("data.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
for(int v=;v<=m;v++) scanf("%d",&ai[i][v]),ci[i][v]=ai[i][v];
}
for(int i=;i<=n;i++)
{
for(int v=;v<=m;v++) dp[v][v]=ai[i][v]*;
for(int k=;k<m;k++)
{
for(int v=;v+k<=m;v++)
{
int l=v,r=v+k;
dp[l][r]=max((dp[l+][r]+ci[i][l])*,(dp[l][r-]+ci[i][r])*);
}
}
ans=dp[][m]+ans;
}
ans.print();
return ;
}
上一篇:AC日记——校门外的树 洛谷 P1047


下一篇:C++的函数重载 转