| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 矩阵取数游戏 | ★☆☆☆☆ | 答案正确 | 100 | 2014/11/15 20:50:25 | 没用高精度（40） |
n*m矩阵，每次取行首或尾的m个数字，每行取数的得分=被取走的元素值*，求可以求出取数后的最大得分。
贪心无效不解释。很容易发现每行之间没有关联，可以看做m组数据，DP的想法仍然是小推大，容易得到DP方程：
CloudLunar
f[from][from+len-1]=max{
(f[from][from+len-2]*2)+f[from+len-1][from+len-1],
(f[from+1][from+len-1]*2)+f[from][from]
}
另外这题要用高精度。
| 1166.cpp代码已折叠
展开折叠内容
|
|---|
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<cstdio>
#define NNN 1000000000
#define nnn 9
using namespace std;
class unsigned_huge_int
{
public:
const size_t size() const
{
return u.size();
}
friend const bool operator <(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
if(a.size()==b.size())
{
for(int i=a.size()-1;i>=0;--i){
if(a.u[i]!=b.u[i])
return a.u[i]<b.u[i];
}
return 0;
}
return a.size()<b.size();
}
friend const bool operator ==(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
if(a.size()==b.size())
{
for(int i=a.size()-1;i>=0;--i){
if(a.u[i]!=b.u[i])
return 0;
}
return 1;
}
return 0;
}
friend const bool operator <=(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
return a<b || a==b;
}
friend const bool operator >(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
return !(a<=b);
}
friend const bool operator >=(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
return !(a<b);
}
friend const bool operator !=(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
return a==b;
}
unsigned_huge_int()
{
u.clear();
u.push_back(0);
}
unsigned_huge_int(const unsigned long long &number)
{
u.clear();
u.push_back(number);
refresh();
}
unsigned_huge_int(const string&original)
{
u.clear();
for(int i=original.size()-1,j=0,p=1;i>=0;--i)
{
j+=(original[i]-'0')*p;
p*=10;
if((!i) || p==NNN)
{
u.push_back(j);
j=0;
p=1;
}
}
}
friend istream& operator >> (istream& os,unsigned_huge_int &ob)
{
string original;
os>>original;
ob=original;
return os;
}
friend ostream& operator << (ostream& os,const unsigned_huge_int &ob)
{
os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1];
for(int i=ob.size()-2;i>=0;--i)
os<<setw(nnn)<<setfill('0')<<ob.u[i];
return os;
}
friend const unsigned_huge_int operator +(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
unsigned_huge_int r;
r.u.resize(max(a.size(),b.size()));
for(int i=0;i<r.size();++i)
{
if(i<a.size())
r.u[i]+=a.u[i];
if(i<b.size())
r.u[i]+=b.u[i];
}
r.refresh();
return r;
}
const unsigned_huge_int d()
{
return *this+*this;
}
friend const unsigned_huge_int operator *(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
if(b==2)
return a+a;
unsigned_huge_int r;
r.u.resize(a.size()+b.size());
for(int i=0;i<a.size();++i)
{
for(int j=0;j<b.size();++j)
{
r.u[i+j]+=a.u[i]*b.u[j];
}
}
r.refresh();
return r;
}
friend const unsigned_huge_int operator -(const unsigned_huge_int &a,const unsigned_huge_int &b)
{
unsigned_huge_int r;
const unsigned_huge_int *p1=&a,*p2=&b;
if(*p1<*p2)
swap(p1,p2);
r.u.resize(p1->size());
for(int i=0;i<r.size();++i)
if(i<p2->size())
r.u[i]+=p1->u[i]-p2->u[i];
else
r.u[i]+=p1->u[i];
r.refresh();
return r;
}
private:
vector<unsigned long long> u;
void refresh()
{
for(int i=0;i<size();++i)
{
if(u[i]>=NNN)
{
if(i==size()-1)
u.push_back(u[i]/NNN);
else
u[i+1]+=u[i]/NNN;
u[i]%=NNN;
}
while(u[i]<0)
{
u[i]+=NNN;
u[i+1]-=1;
}
}
for(int i=size()-1;i!=0;--i)
{
if(u[i]==0&&size()!=1)
{
u.pop_back();
}
}
}
};
unsigned long long n,m;
unsigned_huge_int Ans=0,f[90][90];
int main()
{
scanf("%llu%llu",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
unsigned long long A;
scanf("%llu",&A);
f[j][j]=A;
}
for(int len=2;len<=m;++len)
{
for(int from=1;from+len-1<=m;++from)
{
f[from][from+len-1]=std::max(
(f[from][from+len-2].d())+f[from+len-1][from+len-1],
(f[from+1][from+len-1].d())+f[from][from]
);
}
}
Ans=Ans+(f[1][m].d());
}
cout<<Ans;
}
|