vim复制 editor Python爬虫实战 build vue图表 oracle一键卸载工具 数据库设计规范 html好看的字体 js获取body的高度 python爬虫包 Navicat 二分查找python python3下载安装 pythonset python用什么数据库 java基本类型 jdbc连接mysql java多线程处理 java怎么输出数组 java集成开发环境 h5模板 离散数学及其应用 俄罗斯方块java代码 一键换系统 3d软件下载 abr文件 送货单管理系统 小米8游戏模式 小米9截图 c语言幂函数 谷歌浏览器访问助手 jquery下载 欧洲卡车模拟2存档 德玛上单天赋 mysql关联查询 什么是默认网关 geekbench4 js动画效果 微信小程序抽奖 免费图片转文字软件
当前位置: 首页 > 学习教程  > 编程语言

2019 ICPC Asia Jakarta 问题 J: Tiling Terrace

2020/8/31 14:03:29 文章标签:

题意:给n,k,g1,g2,g3,然后给一个长度为n的只包含’.‘和‘#‘的字符串,
有三种type,
type 1:单个的’.’,贡献为g1,
type 2:两个连着的’.’,贡献为g2.
type 3:".#.",连续的点#点,贡献为g3.
求最优划分使得贡献最大,每个字符只能用于1个type。
字符串中’#'顶多出现50次。
type 1最多用n次。
思路:显然dp,一开始看错了题意以为是个垃圾题,后来发现这个题还是有点东西的。
这一开始感觉应该是个二维dp,但是第一维为字符串前i项,如果第二维为用了j个type1明显是爆了,所以就从#只有50下手,那么明显是第二维代表用了j个type3的最大贡献。但是这样dp是没法处理type 1的类型最多为k个。这时候这个dp最关键的地方就来了,平常的dp一般是直接dp的贡献,但是这个dp[i][j]是代表的前i个字符,构造了j个type 3,能最多搞出来多少type 2,这样dp的话,最后就能通过把一些type2转化为type1来得到最优,而且也能控制type1的个数不大于k。
这种dp之前见过,间接求答案,因为如果dp的贡献是ax+by,然后有一个x+y=n的隐形条件没有用到,但是如果dp的是type2,那么就可以知道x,然后根据隐形条件得到y,然后也可以求贡献,这样即可以控制x和y的大小的目的,又可以得到最终贡献,不过前提是有x+y=n的隐形条件。
ps:加粗的这一段比较抽象。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N=101000;
const int INF=0x3f3f3f3f;
char s[MAX_N];
int dp[MAX_N][55];//代表前i个选了j个type3最多能选多少个type2 
int main(void){
 int n,k,g1,g2,g3,i,j;
 scanf("%d%d%d%d%d",&n,&k,&g1,&g2,&g3);
 scanf("%s",s+1);
 int m=0;
 for(i=1;i<=n;i++){
  if(s[i]=='#')
  m++;
 }
 for(i=0;i<=n;i++){
  for(j=0;j<=m;j++)
  dp[i][j]=-INF;
 }
 dp[0][0]=0;
 for(i=1;i<=n;i++){
  if(i-2>=1&&s[i]=='.'&&s[i-1]=='#'&&s[i-2]=='.'){
   dp[i][0]=dp[i-1][0];
   for(j=1;j<=m;j++)
   dp[i][j]=max(dp[i-1][j],dp[i-3][j-1]);
  }
  else if(s[i]=='#'){
   for(j=0;j<=m;j++)
   dp[i][j]=max(dp[i][j],dp[i-1][j]);
  }
  else if(s[i]=='.'){
   for(j=0;j<=m;j++)
   dp[i][j]=max(dp[i][j],dp[i-1][j]);
   if(i-1>=1&&s[i-1]=='.'){
    for(j=0;j<=m;j++)
    dp[i][j]=max(dp[i][j],dp[i-2][j]+1);
   }
  }
//  for(j=0;j<=m;j++){
//   cout<<i<<" "<<j<<" "<<dp[i][j]<<" !!!\n";
//  }
 }
 int ans=0;
 for(j=0;j<=m;j++){
  if(dp[n][j]<0)
  continue;
  int res=g3*j;
  int p=n-3*j-(m-j);//'.'的个数 
  int q=dp[n][j];
  int ks=0;
  ks=max(ks,q*g2+g1*min(k,p-2*q));
  ks=max(ks,min(k,p)*g1+min(q,(p-min(k,p))/2)*g2);
  if(min(k,p)>=1)
  ks=max(ks,(min(k,p)-1)*g1+min(q,(p-min(k,p)+1)/2)*g2);
  res+=ks;
  ans=max(ans,res);
 }
 printf("%d\n",ans);
 return 0;
} 

本文链接: http://www.dtmao.cc/news_show_150154.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?