自动搬运

查看原文

来自洛谷，原作者为

	zhyh 菜菜菜

搬运于2025-08-24 22:04:25，当前版本为作者最后更新于2018-08-28 17:30:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

代码如下：

#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;
}