30求调(旋棺
查看原帖
30求调(旋棺
892084
xinxin2022楼主2024/7/15 10:48
#include<bits/stdc++.h>
using namespace std;
const int D=1001974;
long long n,c,s,dp[1000005+D+5],v[1000005],w[1000005],minn,maxn;
string r;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>r;
        c=0;s=0;
        for(int j=0;j<r.size();j++){
            if(r[j]=='c') c++;
            if(r[j]=='s') s++;
        }
        w[i]=s-c;
        v[i]=c;
    }
    for(int i=1;i<=n;i++){
        minn=min(minn,minn+w[i]);
        maxn=max(maxn,maxn+w[i]);
        for(int j=minn;j<=maxn;j++){
            dp[j+D]=max(dp[j+D],dp[j-w[i]+D]+v[i]);
        }
    }
    cout<<dp[D];
    return 0;
}
2024/7/15 10:48
加载中...