CFdiv2-Almost Triple Deletions-(正难则反+线性dp)_cf的div2是什么意思

D

题意：
就是给你一个数组，然后对于相邻的两个不同的数，必须删掉他俩，但是删的顺序随意。问你最后最多能剩下多少数。

思考：
很明显，就是删去之后省下的数肯定是相同的。然后数据范围5000，很明显就像是dp了。但是dp该怎么定义呢？刚开始我想dp[i][j]走到i点结尾的数为j的最大可以剩下多少。这样就两重循环了，但是该怎么转移呢？对吧，如果用经典转移又加一重循环，而且第二维度就不要了。直接定义dp[i]以i为结尾的最大可以剩多少。然后转移从前面转移，如果他俩中间的数可以删去，并且i和j的值相同那么可以转移。对于转移的时候，要从合法的状态来转移，如果j前面的数都删不去的话，就没有转移的必要了。对于初始化，如果这个i点前面的数可以全部删去，那么就可以让这个i点为结尾，也就是1。否则是0。当然对于最后，有可能这个数组，是整个必须删完的。所以答案要再从所有的dp里面转移一下，看看转移的这个点，是否能删去后面的所有不要的。对于判断一段区间是否可以删完，就是出现的最大的数是否<=总数/2就可以了，当然总数必须是偶数。

代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 5005,M = 2010;

int T,n,m,k;
int va[N];
int dp[N];
int cnt[N];

int solve()
{
	for(int i=0;i<=n+1;i++)
	{
		dp[i] = 0;
		cnt[i] = 0;
	}
	int maxn = 0;
	for(int i=1;i<=n;i++)
	{
		if((i-1)%2==0&&maxn<=(i-1)/2) dp[i] = 1; //是否可以把前面的删完，这个点当作结尾点
		maxn = max(maxn,++cnt[va[i]]);
	}
	for(int i=1;i<=n;i++)
	{
		maxn = 0;
		for(int j=1;j<=n;j++) cnt[j] = 0;
		for(int j=i-1;j>=1;j--) //直接一遍遍历维护cnt和manx即可，不用弄个二维数组。
		{
			if((i-j-1)%2==0&&maxn<=(i-j-1)/2&&(va[i]==va[j])&&dp[j]>0) //必须要从dp合法的来转移
			{
				dp[i] = max(dp[i],dp[j]+1);
			}
			maxn = max(maxn,++cnt[va[j]]);
		}
	}
	int anw = 0;
	maxn = 0;
	for(int j=1;j<=n;j++) cnt[j] = 0;
	for(int j=n;j>=1;j--) //最后要看看要以哪个结尾，这个数后面的所有数要能删去
	{
		if((n-j)%2==0&&maxn<=(n-j)/2)
		{
			anw = max(anw,dp[j]);
		}
		maxn = max(maxn,++cnt[va[j]]);
	}
	return anw;
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) cin>>va[i];
		cout<<solve()<<"\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

总结：
多多思考呀，dp状态的定义多多尝试。