本鸽子对贪心的理解其实也并不算深
用的相对少，而且也不咋列式子（不要学我）
但是还是很重要（超大声）
今年S的T1想了2.5年，用优先队列AC了（什么鬼）
用来优化的贪心较多（毕竟只是思路）
#include<bits/stdc++.h>
using namespace std;
int n,t;
int maxn = INT_MIN;
int main()
{
cin>>t;
for(int x = 1;x <= t;x++)
{
maxn = 0;
cin>>n;
int a[n+5] = {0},dp[n+5] = {0};
for(int i = 1;i <= n;i++)
cin>>a[i];
for(int i = 1;i <= n;i++)
{
dp[i] = a[i];
for(int j = i-2;j > 0;j--)
{
dp[i] = max(dp[i],dp[j]+a[i]);
}
}
for(int i = 1;i <= n;i++)
maxn = max(maxn,dp[i]);
cout<<maxn<<'\n';
}
return 0;
}
没关系，n²只有1e10（TLE10pts）
那怎么办？
线段树！！！ 必须贪心呀
首先，DP设计肯定不能再优了（只剩一维了）
那就只能从转移入手了
由于题面上说现金都是正整数，那么我们如果可以不影响其他选择，则能多选就多选
如果我们选了 A_5 ,我们就不会只选 A_1 ，因为 A_ 3 可以白选
那么经过观察我们可以发现，我们DP转移范围绝对在i-2~1-3
调一下枚举范围即可
贪心AC
附 · 线段树AC
