[Codeforces 1093F] Vasya and Array | 사유, dp, 배제

제목 대의:

서열 중 -4-1-3-1과 x(1≤x≤m)x(1\lex\lem)x(1≤x≤m)x(1≤x≤m)가 있고, -4-1-1-3-1은 [1,m][1,m][1,m][1,m][1,m] 중 어느 수로 바꿀 수 있는 서열을 제시한다.
하나의 서열이 좋다고 인정하고, 서열의 모든 연속 같은 수의 길이가 l e n len len보다 작을 때만 인정합니다
몇 가지 방안이 이 서열을 좋게 하는지 물어보세요.

제목:

em m m m emmm emmm, 이 dp dp dp는 확실히 좀 어렵습니다. 주로 이런 것을 해 본 적이 없습니다. 정리해 봅시다.
정의

dp[i][j]dp[i][j]dp[i][j]는 앞의 ii 개수를 대표하고 합법적인 마지막 수는 jjj의 방안수이다.

s p [ i ] = ∑ j = 1 m d p [ i ] [ j ] sp[i] =\sum_{j=1}^mdp[i][j] sp[i]=∑j=1m​dp[i][j]

먼저 dp[i][j]=sp[i-3-1]dp[i][j]=sp[i-1]dp[i]=sp[i-3-1]를 명령한다. 그러면 이것은 이미 모든 상황을 포함하고 있다. 즉, 불법 상황이 존재한다는 것을 확신할 수 있다.따라서 불법 상황을 줄이는 것을 고려할 수 있다. 만약에 ii i위를 jjj에 넣는다는 숫자가 확정되면 [i-3-l en+1, i] [i-len+1, i] [i-3-len+1, i]가 모두 -1-1-1-1-1 또는 jj일 때만 현재 불법에 기여할 수 있다.
그래서 먼저 dp[i][j] = sp[i-3-1] - sp[i-3 l en] dp[i] [j] = sp[i-1] - sp[i-len] dp[i] [j] = sp[i-3 1] - sp[i-3 len]
이렇게 해서 [i-al e n + 1, i] [i-len+1, i] [i--len+1, i][i] [i-le e n + 1, i] [i-len+1, i] [i-len+1, i] [i-len+1, i] [i-len]을 같은 수로 나누는 불법 상황을 줄였지만, 이것은 일부를 더 줄였다. 왜냐하면 일부는 이전 i--1-1 i-1의 수에서 제외될 수 있기 때문에 dp[i-[i-l en] [j] dp[i-len] [j] [j] [j] dp[j] dp[j] [i-len] [j] [j][j][j][j][j]]를 [j][j]로 보충해야 한다.
그래서 d p dp dp 전이 방정식:

dp [i] [j] = sp [i-3-1] - sp [i-3 l en] + dp [i-3 l en] [j] dp[i] [j] = sp[i-1] - sp[i-len] + dp[i-len] [j] dp[j] dp[i] [j] [j] = sp[i-1] - sp[i-3 len] + dp[i-3 len] [j], 허용 조건 충족 시 10910

dp [i] [j] = sp [i-3.1] dp[i] [j] = sp[i-1] dp[i] =sp[i-31], 기타

Code:

/*** keep hungry and calm CoolGuang!  ***/
//#pragma GCC optimize(3)
#include 
#include
#include
#include
#include
#include
#define debug(x) cout<
#define dl(x) printf("%lld
",x);
#define di(x) printf("%d
",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const int maxn = 1e6+700;
const int mod= 998244353;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){
     char c=getchar();T x=0,f=1;while(!isdigit(c)){
     if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){
     x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll dp[100005][105];
int sp[100005];
int sum[100005][105];
int a[100005];
int main(){
     
	read(n);read(m);read(p);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++){
     
		for(int k=1;k<=m+1;k++) sum[i][k] = sum[i-1][k];
		sum[i][(a[i]==-1?m+1:a[i])]++;
	}
	sp[0] = 1;

	for(int i=1;i<=n;i++){
     
		if(a[i] == -1){
     
			for(int k=1;k<=m;k++){
     
				dp[i][k] = sp[i-1];
				if(i<p) continue;
				if(sum[i][k]-sum[i-p][k] + sum[i][m+1]-sum[i-p][m+1] == p)
					dp[i][k] = (dp[i][k] - sp[i-p]%mod+mod + dp[i-p][k])%mod;
			}
		}
		else{
     
			for(int k=a[i];k<=a[i];k++){
     
				dp[i][k] = sp[i-1];
				if(i<p) continue;
				if(sum[i][k]-sum[i-p][k] + sum[i][m+1]-sum[i-p][m+1] == p)
					dp[i][k] = (dp[i][k] - sp[i-p]%mod+mod + dp[i-p][k])%mod;
			}
		}
		for(int k=1;k<=m;k++) sp[i] = (sp[i] + dp[i][k])%mod;
	}
	ll ans = 0;
	for(int i=1;i<=m;i++) ans = (ans + dp[n][i])%mod;
		dl(ans);
  return 0;
}

/**
2 2
-1 -2
4 5
**/