【状态设计优化DP】代码源每日一题div1 等差数列

我就是我 2024-03-16 14:48 43阅读 0赞

[等差数列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![64f437cfde1a49f5bda0fc38a1a32aed.png][]

思路：

一看这数据范围，就是个N^2的DP

所以一开始设了个二维的DP，设dp\[i\]\[j\]为，以ai结尾的，等差数列上一个元素为aj的最大长度

但是这样的转移是N^3的，不行

又想了一个dp\[i\]\[j\]表示以ai结尾的，公差为j的等差数列的最大长度，但是这样存不下

总之，常规做法都不行

、

所以，我们要用特殊条件优化状态设计

因为是个等差数列，满足2\*ai==aj+ak

注意到这是个三元组，所以很容易想到去枚举中间那个元素

设dp\[i\]\[j\]为等差数列最后两项为aj,ai的最大长度，枚举ai，双指针j,k，当满足2\*ai==aj+ak时转移、

这是怎么想到的呢？首先考虑刚刚说的那个暴力想法，设dp\[i\]\[j\]为以ai结尾的，等差数列上一个元素为aj的最大长度

然后转移的时候发现要for三层i，j，k,但是考虑三个指针的特殊性：

2\*ai=aj+ak

就会发现很多**无效状态**，我们只需要存满足2\*ai=aj+ak的三个指针i，j，k即可

所以想到枚举三元组进行转移

**这种DP优化永远都是先去考虑暴力DP，再去想用特殊性质对其优化**

**如果是优化状态设计，那么就去考虑有没有无效状态，我们只需要关注什么就好**

**如果是优化转移，就去考虑其他特殊性质**

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=5e3+10;
    
    int N;
    int a[mxn];
    int dp[mxn][mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	sort(a+1,a+1+N);
    	for(int i=1;i<=N;i++){
    		for(int j=i+1;j<=N;j++) dp[i][j]=2;
    	}
    	int ans=-1e9;
    	for(int i=1;i<=N;i++){
    		int L=i-1,R=i+1;
    		while(L>=1&&R<=N){
    			if(2*a[i]==a[L]+a[R]){
    				dp[i][R]=max(dp[i][R],dp[L][i]+1);
    				ans=max(ans,dp[i][R]);
    				L--;
    			}
    			else if(2*a[i]>a[L]+a[R]) R++;
    			else L--;
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/10/problem/843
[64f437cfde1a49f5bda0fc38a1a32aed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9af9fb59466346aeb3b620aa8bfd500c.png