首页 > 代码库 > 【BZOJ】3502 PA2012 Tanie linie
【BZOJ】3502 PA2012 Tanie linie
【算法】
【题解】
胡策k≤10的环状DP做法:
1.钦定法:先确定第一位(可能和第n位)的状态,然后后面正常做DP,显然正确答案是一定会被记录的,因为从整体上看不会有影响。
2.环的特性:取的段和不取的段数量相等,位置互补。所以1和n的连接处都选或都不选都会有不被包括的情况,一选一不选就和链一样了。
正解贪心:
因为相邻的正数或相邻的负数肯定是要选一起选,所以点缩成正负正负…的数列形式,那么考虑先选择全部正的。
如果选择的段数过多,考虑删除则有两种选择:舍弃一个正数(相当于舍弃一个正数和两个负数,把这三个数视为一个负数),选择一个负数(相当于选择一个负数和两个正数,把这三个数视为一个正数)。
那么显然这两种行为是等价的:都是合并相邻的三个数字,可以视为对绝对值最小的数字操作最优,然后过程中用堆动态维护即可。
非环的情况特殊处理:不可能选择头尾的负数,因为没办法合并两个正数,过程中需要判断这个,而且这个头尾还会变化。
对拍还是查找错误相当重要的方式!考试一定要写暴力拍!
据说可以开头特判一些东西跳掉没用个数据——数据是死的,人是活的,出题人是懒的。
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> 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<cyc>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; }
【BZOJ】3502 PA2012 Tanie linie
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。