codeforces1409F Subsequences of Length Two

1618 단어 DP
https://codeforces.com/contest/1409/problem/F
왜 이 문제는 500여 명이 넘으면 난 할 줄 몰라. 100여 줄의 n^3 욕심 예처리를 썼는데 n^3dp는 계속wa야.
마지막으로 사실 dp[i][j][k]를 전 i개의 위치로 설정하고 j번 수정을 했는데 k개 t[0]의 최대 대수가 있어서 상태가 아주 잘 옮겨졌어요.
만약 s[i+1]=t[0]라면 그를 t[0]로 유지하든지 아니면 그가 t[1]로 변하든지
만약 s[i+1]=t[1]이라면, 그를 t[1]로 유지하든지 아니면 t[0]로 변하든지
그렇지 않으면 유지하든지 아니든지 t[0]로 바꾸든지 t[1]로 바꾸든지
t[1]가 변할 때 정답+k, t[0]가 변할 때 k=k+1
#include
using namespace std;

const int maxl=210;

int n,m,cnt,tot,ans;
int dp[maxl][maxl][maxl];
char s[maxl],ss[maxl],t[2];

inline void upd(int &a,int b)
{
	a=max(a,b);
}

inline void prework()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	scanf("%s",t);
}

inline void mainwork()
{
	ans=0;
	if(t[0]==t[1])
	{
		int cnta=0;
		for(int i=1;i<=n;i++)
		if(s[i]==t[0])
			cnta++;
		int mx=min(n,cnta+m);
		ans=mx*(mx-1)/2;
		return;
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0][0]=0;
	for(int i=0;i=0)
			{
				if(s[i+1]==t[0])
				{
					upd(dp[i+1][j][k+1],dp[i][j][k]);
					upd(dp[i+1][j+1][k],dp[i][j][k]+k);
				}
				else if(s[i+1]==t[1])
				{
					upd(dp[i+1][j][k],dp[i][j][k]+k);
					upd(dp[i+1][j+1][k+1],dp[i][j][k]);
				}
				else
				{
					upd(dp[i+1][j][k],dp[i][j][k]);
					upd(dp[i+1][j+1][k],dp[i][j][k]+k);
					upd(dp[i+1][j+1][k+1],dp[i][j][k]);
				}
			} 
	for(int j=0;j<=m;j++)
		for(int k=0;k<=n;k++)
			upd(ans,dp[n][j][k]);
}

inline void print()
{
	printf("%d",ans);
}

int main()
{
	prework();
	mainwork();
	print();
	return 0;
}

좋은 웹페이지 즐겨찾기