dp 优化　F2. Pictures with Kittens (hard version)

本文主要是介绍dp 优化　F2. Pictures with Kittens (hard version)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

dp的优化可能是自己的弱项吧

F1中n*n*n的复杂度强行过去了　

F2就无能为力了；

状态转移

dp[ i ] [ j ] 第一个i存的是位置　　1-n; j是放入数字的个数　　然后F1就暴力过去了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5000+10;
int dp[maxn][maxn];
int a[maxn];
int32_t main()
{int n,k,x; cin>>n>>k>>x;for(int i=1;i<=n;i++) cin>>a[i];dp[0][0]=0;for(int i=1;i<=n;i++){//cout<<"   "<<i<<endl;//cout<<"   "<<i-k+1<<endl;for(int j=i-k;j<i;j++){if(j<0) continue;for(int q=(i-1)/k;q<x;q++){if(dp[j][q]||i<=k)  dp[i][q+1]=max(dp[i][q+1],dp[j][q]+a[i]);}}}int maxn=0;for(int i=n;i>=n-k+1;i--){maxn=max(dp[i][x],maxn);}if(maxn) cout<<maxn<<endl;else  cout<<-1<<endl;
}

暴力的F1

然后F2 gg了

看了别人的代码　　大致有几种写法

双端队列优化　　　deque<pair<int,int> > de[maxn];

写的不难懂点　　　de[ ] [ ] [ ] 　大致就是这样存的　　de[ ] 这个表示的是　存的数字个数　　第二个括号存的是　第i个位置j个数的最大值;　第三个括号存的是　　位置　

第i个位置是由　前[ i-k,i-1 ]位置的地方转移过来的；

从 de[j] 到　de[j+1] 必须确定　　de[j+1] 已经转移了　　所以第二层转移就是 j=x-1; j>=0;j--;

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e3+10;
int a[maxn];
deque<pair<int,int> >  de[maxn];
int32_t main()
{//priority_queue(int,vector<int>,greater<int>) qu;int n,k,x; cin>>n>>k>>x;for(int i=1;i<=n;i++) cin>>a[i];int ans=-1;de[0].push_back({0,0}) ; // first　　cun zhi  second  pos;for(int i=1;i<=n;i++){for(int j=x-1;j>=0;j--){while(!de[j].empty() && de[j].front().second<i-k )  de[j].pop_front(); // i-kif(de[j].empty()) continue;int val=de[j].front().first+a[i];  // jia shang zhe ge shuwhile(!de[j+1].empty() && de[j+1].back().first <=val )  de[j+1].pop_back();de[j+1].push_back({val,i});  // di i  ge wei zhi j+1 ge shu he zui daif(j+1==x&&i+k>n){ans=max(val,ans);}}}cout<<ans<<endl;}