[luogu4158 SCOI2009] 粉刷匠(dp)

Solution

把状态都记上暴力转移即可

Code

//By Menteur_Hxy

#include <queue>

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define Re register

#define Ms(a,b) memset(a,(b),sizeof(a))

#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)

#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

inline LL read() {

	LL x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=51;

int n,m,t,ans;

int f[N][N][N*N][2];

char s[N];

int main() {

	n=read(),m=read(),t=read();

	Fo(i,1,n) {

		scanf("%s",s+1);

		Fo(j,1,m) Fo(k,1,t) {

			if(j==1) {

				f[i][j][k][0]=max(f[i-1][m][k-1][0],f[i-1][m][k-1][1]);

				f[i][j][k][1]=f[i][j][k][0]+1;

			} else {

				if(s[j]==s[j-1]) {

					f[i][j][k][1]=max(f[i][j-1][k][1],f[i][j-1][k-1][0])+1;

					f[i][j][k][0]=max(f[i][j-1][k][0],f[i][j-1][k-1][1]);

				} else {

					f[i][j][k][1]=max(f[i][j-1][k-1][1],f[i][j-1][k][0])+1;

					f[i][j][k][0]=max(f[i][j-1][k-1][0],f[i][j-1][k][1]);

				}

			}

			ans=max(ans,max(f[i][j][k][0],f[i][j][k][1]));

		}

	}

	printf("%d",ans);

	return 0;

}

巴特西

[luogu4158 SCOI2009] 粉刷匠(dp)

Solution

Code

最新文章

热门文章