清橙A1209. 神奇的K线

清橙A1209. 神奇的K线

设保留下来的序列为b;

不难看出，a中至少有一个数没有发生改变且保留在了b中。枚举a中每一个数在b中的位置，此时可以算出b[1]的值。把所有b[1]相同的情况放在一起考虑。

当b[1]确定的时候，设b数组最后一个从a中保留的数位置为maxp，b[maxp]在a中位置为pos，有len个数是从a中保留的。

当modify>=delete时，b数组长度为maxp，最小花费为(maxp-len)*modify+(n-pos+pos-maxp)*delete=(maxp-len)*modify+(n-maxp)*delete

当modify<delete时，最小花费为(n-pos+maxp-len)*modify+(pos-maxp)*delete

发现最小花费只与b中最后一个从a中保留的数以及len有关。

当b[1]相同时枚举以哪一个数在b中哪个位置结尾。len[pos,maxp]=max(len[posj,maxpj](posj<pos&&maxp-maxpj<=pos-posj))

所以按照maxp排序，树状数组维护len值。复杂度(算上map)大概是O(n*n*log2(n*n))，不过一般达不到。

详细细节见代码：

#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{int pos,val;
};
bool cmp(node A,node B)
{return A.val<B.val;
}
int n;
int p[1600];
int a[1600];
int mdi,del,cnt;
map<int,int> mp;
vector<node> vec[1500*1500];
int b[1510];             //树状数组
bool vis[1510];
int stk[1500*1500],ilem;
int lsc[1510];           //临时保存
int lowbite(int x)
{return x&(-x);
}
int qury(int x)
{int re=0;while(x){if(b[x]>re) re=b[x];x-=lowbite(x);}return re;}
void pushin(int x,int v)
{while(x<=n){if(v>b[x]) b[x]=v;if(!vis[x]){vis[x]=1;stk[++ilem]=x;}x+=lowbite(x);}
}
int main(){int s;scanf("%d%d%d",&n,&mdi,&del);for(int i=1;i<=n-1;i++){scanf("%d",&p[i]);p[i]=p[i-1]+p[i];}for(int i=1;i<=n;i++)scanf("%d",&a[i]);int ans=2e9,re,t,delta,len;node st;for(int i=1;i<=n;i++)for(int j=0;j<i;j++){s=a[i]-p[j];t=mp[s];st.pos=i;st.val=j+1;if(!t){mp[s]=++cnt;t=cnt;}vec[t].push_back(st);}int l,r;for(int i=1;i<=cnt;i++){sort(vec[i].begin(),vec[i].end(),cmp);l=0,r=0;while(l<vec[i].size()){while(r+1<vec[i].size()&&vec[i][r+1].val==vec[i][l].val)   //maxp相同的一起处理，保证严格小于r++;for(int j=l;j<=r;j++){s=vec[i][j].pos;len=qury(s-vec[i][j].val+1)+1;lsc[j-l]=len;if(mdi<del){delta=vec[i][j].pos-vec[i][j].val;if(ans>(n-len-delta)*mdi+delta*del)ans=(n-len-delta)*mdi+delta*del;	}else{if(ans>(vec[i][j].val-len)*mdi+(n-vec[i][j].val)*del)ans=(vec[i][j].val-len)*mdi+(n-vec[i][j].val)*del;}}for(int j=l;j<=r;j++){s=vec[i][j].pos;pushin(s-vec[i][j].val+1,lsc[j-l]);}l=r+1;}for(int i=1;i<=ilem;i++){b[stk[i]]=0;vis[stk[i]]=0;}ilem=0;}printf("%dn",ans);return 0;
}
/*
11 2 1
1 2 3 4 5 6 7 8 9 10
0 999 1 6 10 15 21 28 36 45 55
*/