信友队T1求条WA80

问题讨论区 提高段
1

捕获

#include<bits/stdc++.h>
using namespace std;
int dp[5010][5010],a[5010],n;
int main()
{
	memset(dp,0x3f,sizeof dp);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=i;j<=n;j++)
		{
			if(i==j)
			{
				dp[i][j]=0;
				continue;
			}
			dp[i][j]=min(dp[i+1][j]+(a[i]!=a[i+1]&&a[i]!=a[j]),dp[i][j-1]+(a[j]!=a[j-1]&&a[i]!=a[j]));
		}
	}
	cout<<dp[1][n];
}
2

呃，这不是区间DP的板子吗？

3

板子的问题

4

区间dp。

5

wa了

6

对啊，板子问题

7

帮我看看为啥

8

模版不是这样

9

很明显，一定要用区间dp

10

蒟蒻以前写区间dp都用记忆化搜索

11

原来不是CQOI那题啊，我唐了

12

所以如果是板子问题,那到底是哪里出问题了

13 
//初始化
for(int len=2;len<=cnt;len++)//cnt是连通块个数（数组是用连通块存储的），枚举区间长的
    for(int i=1;i+len-1<=cnt;i++){//枚举起点
        int j=i+len-1;//计算终点
        if(a[i]==a[j])//如果连通块相等
            dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1);
        else//连通块不相等
            dp[i][j]=min(dp[i][j],min(dp[i][j-1],dp[i+1][j])+1);
    }
//输出答案
14

O(n^2)

15

平方级别

16

@王峥睿 看我的

17 
//注意：输入要去重，把相邻相同的元素只算一遍，用新的数组保存下来 
for(int len=2;len<=n;len++){
	for(int i=1;i+len-1<=n;i++){
		int j=i+len-1;
		if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1]+1;//不用取min,因为当两头相等时，只有这种情况，直接取中间的状态+1即可 
		else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;//两头不相等，隔出一个，对两种方案取最小值，然后加上1更新 
	}
}//输出 dp[1][n]
18

当i==j时，dp[i][j]=0;
其余初始化为0x3f3f3f3f

19

已AC。吴先回的,解决给他吧

20

不过我还想知道为啥我这样是错的