【算法】贪心，一般DP
【题解】
---
胡策k≤10的环状DP做法：
1.钦定法：先确定第一位(可能和第n位)的状态，然后后面正常做DP，显然正确答案是一定会被记录的，因为从整体上看不会有影响。
2.环的特性：取的段和不取的段数量相等，位置互补。所以1和n的连接处都选或都不选都会有不被包括的情况，一选一不选就和链一样了。
---
正解贪心：
因为相邻的正数或相邻的负数肯定是要选一起选，所以点缩成正负正负…的数列形式，那么考虑先选择全部正的。
如果选择的段数过多，考虑删除则有两种选择：舍弃一个正数(相当于舍弃一个正数和两个负数，把这三个数视为一个负数)，选择一个负数(相当于选择一个负数和两个正数，把这三个数视为一个正数)。
那么显然这两种行为是等价的：都是合并相邻的三个数字，可以视为对绝对值最小的数字操作最优，然后过程中用堆动态维护即可。
非环的情况特殊处理：不可能选择头尾的负数，因为没办法合并两个正数，过程中需要判断这个，而且这个头尾还会变化。
对拍还是查找错误相当重要的方式！考试一定要写暴力拍！
据说可以开头特判一些东西跳掉没用的数据——数据是死的，人是活的，出题人是懒的。
#include#include #include #include using namespace std;const int maxn=1000010;long long a[maxn],n,m,k,b[maxn],pre[maxn],suc[maxn];bool f[maxn];struct cyc{ long long num,ord; bool p; bool operator <(const cyc &a) const { return num>a.num; }}qp;priority_queue q;int main(){ // freopen("input","r",stdin); scanf("%lld%lld",&n,&k); bool now=0;long long tot,m=0; long long ans=0; scanf("%lld",&a[1]); b[(tot=1)]=a[1];now=a[1]>0; for(int i=2;i<=n;i++) { scanf("%lld",&a[i]); if(a[i]>0&&!now) { now=1; b[++tot]=a[i]; } else if(a[i]<=0&&now) { now=0; b[++tot]=a[i]; } else b[tot]+=a[i]; }// if((b[tot]>0)==(b[1]>0)&&tot!=1){b[1]+=b[tot];tot--;}//操作顺序 for(int i=1;i<=tot;i++) { pre[i]=i-1;suc[i]=i+1; if(b[i]>0){ans+=b[i];m++;} q.push((cyc){(b[i]>0?b[i]:-b[i]),i,b[i]>0}); }// pre[1]=tot;suc[tot]=1; suc[tot]=0; long long en=tot,be=1; for(int i=m;i>k;i--) { while(f[q.top().ord]||((q.top().ord==be||q.top().ord==en)&&!q.top().p))q.pop(); qp=q.top();q.pop(); long long sum=0;long long A=pre[qp.ord],B=suc[qp.ord]; if(qp.p)sum=qp.num+b[A]+b[B]; else sum=b[A]+b[B]-qp.num; ans-=qp.num; if(suc[pre[A]])suc[pre[A]]=qp.ord;pre[qp.ord]=pre[A]; if(pre[suc[B]])pre[suc[B]]=qp.ord;suc[qp.ord]=suc[B]; f[A]=f[B]=1;b[qp.ord]=sum; //printf("ord=%lld num=%lld sum=%lld\n",qp.ord,qp.num,sum); if(B==en)en=qp.ord; if(A==be)be=qp.ord; q.push((cyc){(sum>0?sum:-sum),qp.ord,sum>0}); } printf("%lld",ans);//开long long return 0;}