题解 P4832 【珈百璃堕落的开始】

· · 题解

比赛时写的程序开了o2后跑了286ms，竟然是目前第一233
思想仍然是背包，但是和赛后题解里的处理有些不同，常数更小一些qwq
我们记一个式子的s和c的个数分别为a、b，则不妨令体积v=a-b，那么答案就是体积为0时的最大价值w了。其实由对称性，也可以令所有v=b-a。那么价值呢？全部设为w=a或全部w=b都可以啦，个人觉得这样处理还是挺漂亮的qwq
于是就成了带有负数体积的背包问题啦，和P2079类似，我们只需要处理一下数组下标越界的问题，因此我们把所有下标平移一个足够大的T就可以了，其他照常写。另外由于有负数体积，直接滚动数组就会有后效性了，改为取膜滚动也无妨。方程：

dp[i][j+T] = max(dp[i][j+T], dp[i-1][j-v+T]+w)

代码如下：

#include <cstdio>
#include <cstring>
using namespace std;

const int inf = 100000000;
const int T = 1000300;
int N, sum[2], dp[2][2001005], l, r;
char s[2000005];

inline int max(int x, int y)
{
    return x>y? x: y;
}
inline int min(int x, int y)
{
    return x<y? x: y;
}
int main()
{
    scanf("%d", &N);
    for (register int i=0; i<=2001000; ++i) dp[0][i] = dp[1][i] = -inf;
    dp[0][T] = 0;
    for (register int i=1, ls; i<=N; ++i) {
        scanf("%s", s), ls = strlen(s);
        sum[0] = 0, sum[1] = 0;
        for (register int j=0; j<ls; j+=2) if (s[j]=='c') sum[0]++; else sum[1]++;
        int w = sum[0], v = sum[1] - sum[0];
        l = min(l, l+v), r = max(r, r+v);
        for (register int j=l; j<=r; j++) {
            dp[i&1][j+T] = max(dp[i&1][j+T], dp[i&1^1][j+T]);
            dp[i&1][j+T] = max(dp[i&1][j+T], dp[i&1^1][j-v+T]+w);
            //printf("%d: %d\n", j, dp[i&1][j+T]);
        }
    }
    printf("%d\n", dp[N&1][T]);
    return 0;
}