ccpc 3-21训练心得
今天和队友补了两题 分别是 B 和 D
这题挺搞笑的。用的是动态规划，动态规划方程为
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;
此题思路主要是动态规划的倒推，值得学习
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 两个参数分别表示 当前数组的和，以及编号
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;
}
此题主要使用优先队列，当一个每个元素都是大于或等于0的数组来说：
最长子序列肯定为它本身，第二长子序列肯定在最长子序列之中。
所以便可用优先队列求解：
先把最长压入队列，然后pop出来，把减去左右两个分别压入。
并且做好记号防止重复压入。
只要弹出w次即可。
