CF1252J Tiling Terrace
CF1252J Tiling Terrace
题目描述
Talia has just bought an abandoned house in the outskirt of Jakarta. The house has a nice and long yard which can be represented as a one-dimensional grid containing 1 \times N1×N cells. To beautify the house, Talia is going to build a terrace on the yard by tiling the cells. Each cell on the yard contains either soil (represented by the character '.') or rock (represented by the character '#'), and there are at most 5050 cells containing rocks.
Being a superstitious person, Talia wants to tile the terrace with mystical tiles that have the power to repel ghosts. There are three types of mystical tiles:
- Type-1: Covers 1 \times 11×1 cell and can only be placed on a soil cell (".").
- Type-2: Covers 1 \times 21×2 cells and can only be placed on two consecutive soil cells ("..").
- Type-3: Covers 1 \times 31×3 cells and can only be placed on consecutive soil-rock-soil cells (".#.").
Each tile of Type-1, Type-2, and Type-3 has the power to repel G_1G1 , G_2G2 , and G_3G3 ghosts per day, respectively. There are also some mystical rules which must be followed for the power to be effective:
- There should be no overlapping tiles, i.e. each cell is covered by at most one tile.
- There should be at most KK tiles of Type-1, while there are no limitations for tiles of Type-2 and Type-3.
Talia is scared of ghosts, thus, the terrace (which is tiled by mystical tiles) should be able to repel as many ghosts as possible. Help Talia to find the maximum number of ghosts that can be repelled per day by the terrace. Note that Talia does not need to tile all the cells on the yard as long as the number of ghosts that can be repelled by the terrace is maximum.
输入格式
Input begins with a line containing five integers: NN KK G_1G1 G_2G2 G_3G3 ( 1 \le N \le 100,0001≤N≤100000 ; 0 \le K \le N0≤K≤N ; 0 \le G_1, G_2, G_3 \le 10000≤G1,G2,G3≤1000 ) representing the number of cells, the maximum number of tiles of Type-1, the number of ghosts repelled per day by a tile of Type-1, the number of ghosts repelled per day by a tile of Type-2, and the number of ghosts repelled by a tile of Type-3, respectively. The next line contains a string of NN characters representing the yard. Each character in the string is either '.' which represents a soil cell or '#' which represents a rock cell. There are at most 5050 rock cells.
输出格式
Output in a line an integer representing the maximum number of ghosts that can be repelled per day.
输入输出样例
输入 #1复制
输出 #1复制
输入 #2复制
输出 #2复制
输入 #3复制
输出 #3复制
说明/提示
Explanation for the sample input/output #1
Let "A" be a tile of Type-1, "BB" be a tile of Type-2, and "CCC" be a tile of Type-3. The tiling "ACCCBB" in this case produces the maximum number of ghosts that can be repelled, i.e. 10 + 40 + 25 = 7510+40+25=75
Explanation for the sample input/output #2
This sample input has the same yard with the previous sample input, but each tile of Type-2 can repel more ghosts per day. The tiling "BB#BBA" or "BB#ABB" produces the maximum number of ghosts that can be repelled, i.e. 100 + 100 + 10 = 210100+100+10=210 . Observe that the third cell is left untiled.
Explanation for the sample input/output #3
The tiling "ACCCA.#", "ACCC.A#", or ".CCCAA#" produces the maximum number of ghosts that can be repelled, i.e. 30 + 100 + 30 = 16030+100+30=160 . Observe that there is no way to tile the last cell.
题解:
非常容易判断是一道\(DP\)的题目。
联想一下这道题目:CF358D Dima and Hares
那么我们分方式决策,可以看出:第一种和第二种的选择都仅包含".",只有第三种选择有"#",那么我们可以考虑分段进行决策:将整个序列分成以"#"相隔开的段,并用\(a[i]\)数组保存\(i\)段中"."的个数。
那么我们设置状态\(dp[i][j][0/1]\)表示前\(j\)段用了\(i\)次方式\(1\),后面的\(0/1\)表示最后的"#"有没有用方式\(3\)所获得的最大价值。
那么我们转移的时候就只需要考虑方式二的使用次数。
转移方程需要分类讨论。另外地,还有一种情况是不选择完这\(n\)个字符。这个东西可以在枚举方式1的时候用除以二自动取整来实现。
可以结合代码理解:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1e5+10;
int n,k,g1,g2,g3,tot,ans;
char s[maxn];
int a[maxn],dp[60][maxn][5];
//dp[i][j][0/1]表示前j段使用i次方式1,最后一个"#"是否选用方式3所得的最大利益。
signed main()
{
scanf("%I64d%I64d%I64d%I64d%I64d",&n,&k,&g1,&g2,&g3);
scanf("%s",s+1);
tot=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='#')
tot++;
else
a[tot]++;
}
while(tot && !a[tot])
tot--;
if(!tot)
{
puts("0");
return 0;
}
memset(dp,0xcf,sizeof(dp));
dp[0][0][0]=0;
for(int i=1;i<=tot;i++)
for(int j=0;j<=k;j++)
{
int t=min(a[i],j);
for(int l=0;l<=t;l++)
{
if(l<=a[i])
dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-l][0]+(a[i]-l)/2*g2+l*g1);
if(l<=a[i]-1)
{
dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-l][1]+(a[i]-l-1)/2*g2+g3+l*g1);
dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-l][0]+(a[i]-l-1)/2*g2+l*g1);
}
if(l<=a[i]-2)
dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-l][1]+(a[i]-l-2)/2*g2+g3+l*g1);
}
}
for(int i=0;i<=k;i++)
ans=max(ans,dp[tot][i][0]);
printf("%I64d",ans);
return 0;
}
最新文章
- Angularjs学习笔记(四)----与后端服务器通信
- MySQL	存储过程学习笔记
- 每天进步一点点——负载均衡之DNS域名解析
- go官网教程A Tour of Go
- 优化移动体验的HTML5技巧
- sql server数据库查询同义词
- pom 的scope标签分析
- 编写高质量的JavaScript代码(一)
- springboot redis 缓存对象
- Java Web基础入门
- [BZOJ2733] [HNOI2012] 永无乡 (splay启发式合并)
- http的CA证书安装(也就是https)
- 【easy】278. First Bad Version
- 两种方法操作其它mac应用的窗口
- Matlab - 各种函数学习
- AntDesign从入门到精通
- json排序 及替换在字符串中全部替换某字符串
- SpringBoot document notes
- 初学者须知 常见的HTML5开发工具有哪些
- 使用kubeadm安装kubernetes高可用集群