Easy Game LightOJ - 1031
2018-06-27 10:03:52来源:未知 阅读 ()
Easy Game LightOJ - 1031
upd:似乎有复杂度更优越的做法,见http://www.cnblogs.com/hehe54321/p/8431020.html
题意:A和B玩一个游戏,A先手。规则是两人轮流在当前数列的任意一端取走任意个数(但不能两端都取),然后把这些数的和加到自己的得分上,直到数列被取完。如果两人都采取最优策略,那么A比B最多能多得多少分?
sum(l,r)表示原数列l到r范围内的数之和。ans[l][r]表示要取完l到r区间的数,先手的人可以得到的比对手多的最大得分。
那么,如果l==r,也就是只有一个,那么他必须取这一个,ans[l][r]=sum(l,r)。
否则,他可以选择在左侧取走第l个到第i个,那么自己得到sum(l,i),之后对手按照最优策略能比自己多ans[i+1][r]分,那么ans[l][r]=max{sum(l,i)-ans[i+1][r]}。他也可以选择在右侧取走第i个到第r个,那么自己得到sum(i,r),之后对手按照最优策略比自己多ans[l][i-1],那么ans[l][r]=max{sum(i,r)-ans[l][i-1]}。他也可以选择全部选完,那么ans[l][r]=sum(l,r)。最后答案就是上述三种中最大的一种。时间复杂度$O(n^3)$。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int sum[110],ans[110][110],a[110],T,TT,n; 6 int getsum(int l,int r) 7 { 8 return sum[r]-sum[l-1]; 9 } 10 int get(int l,int r) 11 { 12 if(ans[l][r]) return ans[l][r]; 13 int i,maxans=getsum(l,r); 14 for(i=l;i<r;i++) 15 maxans=max(maxans,getsum(l,i)-get(i+1,r)); 16 for(i=r;i>l;i--) 17 maxans=max(maxans,getsum(i,r)-get(l,i-1)); 18 return ans[l][r]=maxans; 19 } 20 int main() 21 { 22 int i; 23 scanf("%d",&T); 24 for(TT=1;TT<=T;TT++) 25 { 26 memset(a,0,sizeof(a)); 27 memset(sum,0,sizeof(sum)); 28 memset(ans,0,sizeof(ans)); 29 scanf("%d",&n); 30 for(i=1;i<=n;i++) 31 scanf("%d",&a[i]); 32 for(i=1;i<=n;i++) 33 sum[i]=sum[i-1]+a[i]; 34 printf("Case %d: %d\n",TT,get(1,n)); 35 } 36 return 0; 37 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:N Queen Again LightOJ - 1061
下一篇:sizeof
- CF1215DTicketGame——(博弈) 2020-04-25
- AtCoder agc007_d Shik and Game 2020-02-08
- 《游戏引擎构架Game Engine Architecture》略读笔记 2019-09-23
- kuangbin专题 专题一 简单搜索 Fire Game FZU - 2150 2019-08-16
- D - Dice Game (BFS) 2019-02-27
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash