AtCoder Regular Contest 164 D.1D Coulomb(dp)

题目

原题意描述比较复杂，但是可以被替换成一个等价的题：

一个由?、+、-构成的长度为2n(n<=3000)的串，?可以填+或-，

合理地填写?，使得串中恰有n个+，n个-

求所有的合法填写方案下，+-均贪心匹配时，所有对+-之间的距离和

答案对998244353取模

思路来源

赛中AC

题解

感觉维护一个方案数，维护一个总和已经是典中典中典了

dp[i][j]表示考虑前i个字母，+比-多j个的方案数，

sum[i][j]表示前i个字母，+比-多j个时，所有方案的距离和

可以发现，每经过一个字母，还有j个字母没匹配时，

这里的没匹配，既可以是+比-多j个，也可以是+比-少j个，

对应的方案数为dp[i][j]，对总距离和的贡献为dp[i][j]*j

如果是合法栈匹配，只转移正的就可以了，

但是本题中，正负的转移都是合法的

因为有负值，所以要将下标偏移一下，

按每一位字母，三种情况，转移即可

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
const int N=3e3+10,M=2*N,mod=998244353;
int n,dp[M][M],sum[M][M];
char s[M];
void add(int &x,int y){
	x=(x+y)%mod;
}
int main(){
	sci(n);
	scanf("%s",s+1);
	dp[0][N]=1;
	int m=n*2;
	rep(i,1,m){
		if(s[i]=='+'){
			rep(j,N-i,N+i){
				add(dp[i][j],dp[i-1][j-1]);
				add(sum[i][j],sum[i-1][j-1]);
			}
		}
		else if(s[i]=='-'){
			rep(j,N-i,N+i){
				add(dp[i][j],dp[i-1][j+1]);
				add(sum[i][j],sum[i-1][j+1]);
			}
		} 
		else{
			rep(j,N-i,N+i){
				add(dp[i][j],(dp[i-1][j+1]+dp[i-1][j-1])%mod);
				add(sum[i][j],(sum[i-1][j+1]+sum[i-1][j-1])%mod);
			}
		}
		rep(j,N-i,N+i){
			add(sum[i][j],1ll*dp[i][j]*abs(j-N)%mod);
		}
		// rep(j,0,i){
		// 	printf("i:%d j:%d dp:%d sum:%d\n",i,j,dp[i][j],sum[i][j]);
		// }
	}
	pt(sum[m][N]);
	return 0;
}