今天和隊友補了兩題 分別是 B?和 D

? ? 這題挺搞笑的。用的是動態(tài)規(guī)劃，動態(tài)規(guī)劃方程為

dp[i]= max(dp[i+1],dp[i+d+1]+a[i])? ,a[i]>=w;

dp[i]=dp[i+1]+a[i];a[i]<w;

此題思路主要是動態(tài)規(guī)劃的倒推，值得學(xué)習(xí)

code:

#include<bits/stdc++.h>

using namespace std;

long long a[int(1e5+1)],dp[int(2e5+1)];

int main(){

long long n,d,m;

cin>>n>>d>>m;

for(int i=0;i<n;i++){

cin>>a[i];

}

for(int i = n-1;i>=0;i--) {

if(a[i]<=m){

dp[i]=dp[i+1]+a[i];

} else {

dp[i]=max(dp[i+1],a[i]+dp[i+d+1]);

}

}

cout<<dp[0];

}

code:

#include<bits/stdc++.h>

using namespace std;

int n,w;

priority_queue<pair<long long, pair<int,int> > >Q;

//pair 兩個參數(shù)分別表示 當前數(shù)組的和，以及編號

map<pair<int,int> , int> sign;

long long sum,a[100005];

int main()

{

? ? cin>>n>>w;

? ? for(int i=1;i<=n;i++)

? ? {

? ? ? ? cin>>a[i];

? ? ? ? sum+=a[i];

? ? ? ? // auto t=Q.top();

? ? ? ? // cout<<t.second.second<<endl;

? ? }

? ? Q.push({sum,{1,n}});

? ? while(Q.size()&&w)

? ? {

? ? ? w--;

? ? ? auto t = Q.top(); // 自動變量

? ? ? Q.pop();

? ? ? cout<<t.first<<' '; //為 pair第一個元素

? ? ? //cout<<t.second.first<<t.second.second<<endl?

? ? ? if(t.second.first+1 <= t.second.second && !sign[{t.second.first+1,t.second.second}])

? ? ? {

? ? ? ? Q.push( { t.first - a[t.second.first] , {t.second.first+1, t.second.second} } );

? ? ? ? sign[{t.second.first+1,t.second.second}] = 1;

? ? ? }

? ? ? if(t.second.first <= t.second.second-1 && !sign[{t.second.first,t.second.second-1}])

? ? ? {

? ? ? ? Q.push( { t.first - a[t.second.second] , {t.second.first, t.second.second-1} } );

? ? ? ? sign[{t.second.first,t.second.second-1}] = 1;

? ? ? }

? ? }

? ? return 0;

}

此題主要使用優(yōu)先隊列，當一個每個元素都是大于或等于0的數(shù)組來說：

最長子序列肯定為它本身，第二長子序列肯定在最長子序列之中。

所以便可用優(yōu)先隊列求解：

先把最長壓入隊列，然后pop出來，把減去左右兩個分別壓入。

并且做好記號防止重復(fù)壓入。

只要彈出w次即可。