[luogu] CF455A Boredom 值域dp

前言

传送门 :

题目大意

给定 n n n长度的数组 a a a,你可以任意次操作

对于每次操作 :

• 如果当前选 x x x,则数组中所有的 x + 1 , x − 1 x+1,x-1 x+1,x−1 都被清空 , a n s + = x ans+=x ans+=x

求最大的 a n s ans ans

思路

状态表示 : d p [ i ] dp[i] dp[i] 当前位置为 i i i的最大 a n s ans ans 状态计算 : d p [ i ] = m a x ( d p [ i − 1 ] , d p [ i − 2 ] + c n t [ i ] ∗ i ) dp[i] = max(dp[i-1],dp[i-2]+cnt[i]*i) dp[i]=max(dp[i−1],dp[i−2]+cnt[i]∗i)

为什么这样子是正确的呢 ? 是否满足题目中的 x + 1 x+1 x+1也被清空了呢 ? ? ?

• d p [ i ] = d p [ i − 1 ] dp[i]=dp[i-1] dp[i]=dp[i−1]说明 i i i没有被选中,从 i − 1 i-1 i−1转移
• d p [ i ] = d p [ i − 2 ] + c n t [ i ] ∗ i dp[i] =dp[i-2]+cnt[i]*i dp[i]=dp[i−2]+cnt[i]∗i说明选中了当前点,因此无法从 i − 1 i-1 i−1转移

因此如果 d p [ i ] = d p [ i − 2 ] + c n t [ i ] ∗ i dp[i]=dp[i-2]+cnt[i]*i dp[i]=dp[i−2]+cnt[i]∗i的话,对于下一个点 i + 1 i+1 i+1不管是从 i − 2 i-2 i−2转移还是从 i − 1 i-1 i−1转移都满足了 x + 1 x+1 x+1被清空了

这题因为考虑 x + 1 x+1 x+1就没考虑 d p dp dp,一眼后效性,因此直接暴力结果 T T T飞了

Mycode

map mp;
const int  N  = 1e5+10;

ll dp[N];
int n;

void solve(){
	cin>>n;
	int maxn = -1;
	
	for(int i=1;i>x;
		mp[x]++;
		maxn = max(maxn,x);
	}
	
	dp[1] = mp[1];
	for(int i=2;i