注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

248  

2016-04-22 17:23:16|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    Bessie 近一段迷上了一款游戏。这个游戏一开始会给你N个1到40的数字。她可以将两个相邻且相等的数字合并成一个比原来大1的数字(比如她可以将两个连续的7合并成一个8)游戏的最后得分是游戏结束时序列中最大的数字。请帮助Bessie算出她可以得到的最高分数。
    输入:
    第一行是一个整数N(N<=248),接下来N行每行一个数字,表示游戏开始时的序列
    输出:
    一个数字,表示Bessie的最大得分
==========================================================================
    用动态规划做,这里用了区间DP和一个状态拆分。
    状态:f[i][j][k]表示i~j中能否组成k。
    子问题:f[i][j][k]=1 --> (f[i][mid][k-1]=1 && f[mid+1][j][k-1]=1)(枚举mid)
    边界:当i==j时f[i][j][a[i(j)]]=1。(a数组记录原数)
==========================================================================
程序:
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

int a[500];

int f[300][300][50];

int main()
{
freopen("248.in","r",stdin);
freopen("248.out","w",stdout);
int n; scanf("%d",&n);
for (int i=0; i<n; i++) scanf("%d",&a[i]);
int ans=0;
for (int j=0; j<=n; j++)
 for (int i=0; i+j<n; i++)
 {
  if (j==0) f[i][i+j][a[i]]=1;
 
  for (int k=i; k<i+j; k++)
   for (int p=0; p<=40; p++)
    if (f[i][k][p]==1 && f[k+1][i+j][p]==1)
   f[i][i+j][p+1]=1,ans=max(ans,p+1);
 }
cout<<ans;
return 0;
}
==========================================================================
白金变态,不谈。

  评论这张
 
阅读(4)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018