题目链接
洛谷 P4832 珈百璃堕落的开始
模板：背包题型
思路分析
首先，根据提示，结果为整数即为 s 和 c 的个数一样，最大整数答案即为在此前提下 s 的个数。所以，对于这些式子，我们先求出其中 s 和 c 的个数，然后以个数的差值为物品代价，以 s 的个数为物品价值，答案为总个数差值为 \(0\) 时的最大价值。所以这题就变为了有负代价的背包问题，详见洛谷 P2340 题解。这里给出另一种做法：
还是先将下标加上数据范围，这里为 \(10^6\)，总下标即为 \(0\sim 2\times 10^6\)。然后，对于滚动数组优化，由于存在负代价，可能会使用已经更新过的数据（减去负值即为加上一个正值），所以可以如链接中所说分类处理，或者保留上一层结果，如代码中 dp[2][M]，考虑 dp[i][] 时，其所需要调用的 dp[i^1][] 未被修改。
优化
但是，若直接全部循环，时间复杂度可以卡至 \(O(10^{14})\)，明显会 T，考虑优化。我们发现，\(n\times m\) 的数据规模可以通过，但是题目中没有给出 \(n\) 的范围，说明正解应跟 \(n\times m\) 整体有关。我们发现，每次都全部循环，可能有些下标不可能实现，我们可以动态更新每次循环的上下界，就是一道经典的贪心题：
给定数列 \(a_{[1..n]}\)，从中选出一些数求选出来的数的和的最大值
得到结果之后，我们从初始状态 \(dp_{10^6}\) 向两边扩展即可，时间复杂度优化为 \(O(nm)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;const int M=2e6+10;
int n,m;
int dp[2][M]; // 滚动数组优化int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;memset(dp,-0x3f,sizeof dp);dp[0][int(1e6)]=dp[1][int(1e6)]=0;int l=1e6,r=1e6;for (int i=1;i<=n;++i){string s; cin>>s;int cnt1=0,cnt2=0; // s,c 的数量for (auto j:s){if (j=='s') ++cnt1;else if (j=='c') ++cnt2;}int cnt=cnt1-cnt2;m+=cnt1+cnt2,l=min(l,l+cnt),r=max(r,r+cnt);for (int j=l;j<=r;++j) // 左右边界！！！dp[i&1][j]=max(max(dp[i&1][j],dp[(i&1)^1][j]),dp[(i&1)^1][j-cnt]+cnt1);}printf("%d",dp[n&1][int(1e6)]);return 0;
}