Codeforces 1107E (Vasya and Binary String) (记忆化，DP + DP)
|
题意：给你一个长度为n的01串，和一个数组a，你可以每次选择消除一段数字相同的01串，假设消除的长度为len，那么收益为a[len]，问最大的收益是多少? 思路：前两天刚做了POJ 1390，和此题很相似：POJ 1390?。我们甚至可以直接套用这个题的状态转移方程。仍然先把01串预处理一下，把相邻的并且数字相同的位合并成一个块。这样，01串就变成了若干个相邻的01块了。 设dp[i][j][k]为处理第i个块到第j个块，并且后面有k个位和第j个块颜色相同，设f[i]为消除长度为i的串的最大收益，那么状态转移方程可以这样写： 1:先把后面相同的合并了：dp[i][j][k] = max(dp[i][j][k],dp[i][j - 1][0] + f[第j个块的位的个数 + k]。 2:与前面的颜色相同的块合并(假设块j与块p颜色相同)：dp[i][j][k] = max(dp[i][j][k],dp[i][p][k +?第j个块的位的个数] + dp[p + 1][j - 1][0]); 现在唯一的问题f数组怎么求？很明显此题并不是一次消除的长度越长越好，多次消除短的串可能获得更高的收益。我们可以思考一下，f[i]肯定是把长度i拆成1份，2份，......i份中收益最大的情况。 设re[i][j]为把长度j拆成i份获得的最大收益，我们可以暴力枚举第i份的长度是多少（假设是k），然后继续递归去求得把j - k拆成i - 1份的最优值来更新当前状态。那么f[i]就是re[1][i],re[2][i].....re[i][i]中的最优情况。 dp和re数组我们都可以记忆化，可以大幅度提高效率，31ms水过。。。 代码： #include <bits/stdc++.h>
#define LL long long
using namespace std;
LL dp[110][110][110];
bool v[110][110][110],v1[110][110];
LL f[110],b[110];
LL re[110][110];
struct node{
int flag,cnt;
};
node a[110];
LL get_f(int tot,int n) {
if(v1[tot][n]) return re[tot][n];
if(tot == 1) {
v1[tot][n] = 1;
return re[tot][n] = f[n];
}
else {
LL ans = 0;
for (int i = 1; i <= n - tot + 1; i++) {
ans = max(ans,f[i] + get_f(tot - 1,n - i));
}
v1[tot][n] = 1;
return re[tot][n] = ans;
}
}
int cal(int n) {
LL ans = 0;
f[n] = b[n];
for (int i = 1; i <= n; i++) {
ans = max(ans,get_f(i,n));
}
f[n] = ans;
}
LL solve(int l,int r,int x) {
if(v[l][r][x]) return dp[l][r][x];
if(l >= r) return f[a[r].cnt + x];
LL ans = solve(l,r - 1,0) + f[a[r].cnt + x];
for (int i = l; i < r; i++) {
if(a[i].flag == a[r].flag) {
ans = max(ans,solve(l,i,a[r].cnt + x) + solve(i + 1,0));
}
}
v[l][r][x] = 1;
return dp[l][r][x] = ans;
}
int main() {
int n;
char s[210];
scanf("%d",&n);
scanf("%s",s + 1);
int now_flag = -1,now = 0,tot = 0;
for (int i = 1; i <= n; i++) {
if(s[i] - ‘0‘ != now_flag) {
a[++tot].flag = s[i] -‘0‘;
a[tot].cnt = 1;
now_flag = s[i] - ‘0‘;
} else {
a[tot].cnt++;
}
}
for (int i = 1; i <= n; i++) {
scanf("%lld",&b[i]);
}
for (int i = 1; i <= n; i++)
cal(i);
printf("%lldn",solve(1,tot,0));
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |