CloudLunar
主页
知识库
人文社科
自然科学
跨学科领域
热门分类
算法及题库
云璟月's
墨色集(设计)
指尖集(代码)
未央集(随笔)
流觞集(语录)
如花集(书影)
纸鸢集(小说)
登录
B站
微博
人人
开心
Twitter
Facebook
RSS订阅链接
留言板
关于我
在社交网站上关注我
B站
微博
人人
开心
Twitter
Facebook
RSS订阅
RSS订阅链接
留言板
关于我
查看CodeVS/1166的源代码
←
CodeVS/1166
因为以下原因,你没有权限编辑本页:
你刚才请求的操作只对属于该用户组的用户开放:
用户
您可以查看并复制此页面的源代码:
[[分类:区间动态规划]] ==摘要== {{信息题|矩阵取数游戏|http://www.codevs.cn/problem/1166/|1|100|time=2014/11/15 20:50:25|没用高精度|40}} ==题意== n*m矩阵,每次取行首或尾的m个数字,每行取数的得分=被取走的元素值*<m>2^i</m>,求可以求出取数后的最大得分。 ==题解== 贪心无效不解释。很容易发现每行之间没有关联,可以看做m组数据,DP的想法仍然是小推大,容易得到DP方程: <pre> 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] } </pre> 另外这题要用高精度。 ==代码== {{折叠|1166.cpp代码已折叠 |<pre> #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; } </pre> |code1166}}
该页面使用的模板:
模板:信息题
(
查看源代码
)
模板:折叠
(
查看源代码
)
返回
CodeVS/1166
。
著作权声明
[
编辑
]
除非另有说明,本
网站内容
采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
进行许可(中国大陆可以参照
知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议
,如有不同以前者为准)。
如果需要商业化使用,请另联系作者取得授权。
关于
[
编辑
]
联系
@云璟月Lunar
的新浪微博
本站RSS:
RSS链接