bzoj4873 [Shoi2017]寿司餐厅

bzoj4873 [Shoi2017]寿司餐厅

​​ Description

Kiana最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上，这家餐厅都会按顺序提供n种寿司，第i种寿司有一个 代号ai和美味度di,i，不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的，Kiana也可以无限次 取寿司来吃，但每种寿司每次只能取一份，且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段，即Kiana 可以一次取走第1,2种寿司各一份，也可以一次取走第2,3种寿司各一份，但不可以一次取走第1,3种寿司。由于餐 厅提供的寿司种类繁多，而不同种类的寿司之间相互会有影响：三文鱼寿司和鱿鱼寿司一起吃或许会很棒，但和水 果寿司一起吃就可能会肚子痛。因此，Kiana定义了一个综合美味度di,j(i< j)，表示在一次取的寿司中，如果包含 了餐厅提供的从第i份到第j份的所有寿司，吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一 些时间，所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时，不止一个综合美味度会被 累加，比如若Kiana一次取走了第1,2,3种寿司各一份，除了d1,3以外，d1,2,d2,3也会被累加进总美味度中。神奇 的是，Kiana的美食评判标准是有记忆性的，无论是单种寿司的美味度，还是多种寿司组合起来的综合美味度，在 计入Kiana的总美味度时都只会被累加一次。比如，若Kiana某一次取走了第1,2种寿司各一份，另一次取走了第2,3 种寿司各一份，那么这两次取寿司的总美味度为d1,1+d2,2+d3,3+d1,2+d2,3，其中d2,2只会计算一次。奇怪的是， 这家寿司餐厅的收费标准很不同寻常。具体来说，如果Kiana一共吃过了c(c>0)种代号为x的寿司，则她需要为这些 寿司付出mx^2+cx元钱，其中m是餐厅给出的一个常数。现在Kiana想知道，在这家餐厅吃寿司，自己能获得的总美 味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。由于她 不会算，所以希望由你告诉她 Input

第一行包含两个正整数n,m，分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。 第二行包含n个正整数，其中第k个数ak表示第k份寿司的代号。 接下来n行，第i行包含n-i+1个整数，其中第j个数di,i+j-1表示吃掉寿司能 获得的相应的美味度，具体含义见问题描述。 N<=100,Ai<=1000

Output

输出共一行包含一个正整数，表示Kiana能获得的总美味度减去花费的总钱数的最大值。

Sample Input

3 1 2 3 2 5 -10 15 -10 15 15 Sample Output

12 【样例1说明】 在这组样例中，餐厅一共提供了3份寿司，它们的代号依次为a1=2，a2=3，a3=2，计算价格时的常数m=1。在保证每 次取寿司都能获得新的美味度的前提下，Kiana一共有14种不同的吃寿司方案： 1.Kiana一个寿司也不吃，这样她获得的总美味度和花费的总钱数都是0，两者相减也是0； 2.Kiana只取1次寿司，且只取第1个寿司，即她取寿司的情况为{[1,1]}，这样获得的总美味度为5，花费的总钱数 为1-2^2+1*2=6，两者相减为-1； 3.Kiana只取1次寿司，且只取第2个寿司，即她取寿司的情况为{[2,2]}，这样获得的总美味度为-10，花费的总钱 数为1-3^2+1*3=12，两者相减为-22； 4.Kiana只取1次寿司，且只取第3个寿司，即她取寿司的情况为{[3,3]}，这样获得的总美味度为15，花费的总钱数 为1*2^2+1*2=6，两者相减为9； 5.Kiana只取1次寿司，且取第1,2个寿司，即她取寿司的情况为{[1,2]}，这样获得的总美味度为5+(-10)+(-10)=-1 5，花费的总钱数为(1-2^2+1*2)+(1-3^2+1*3)=18，两者相减为-33； 6.Kiana只取1次寿司，且取第2,3个寿司，即她取寿司的情况为{[2,3]}，这样获得的总美味度为(-10)+15+15=20， 花费的总钱数为(1-2^2+1*2)+(1*3^2+1*3)=18，两者相减为2； 7.Kiana只取1次寿司，且取第1,2,3个寿司，即她取寿司的情况为{[1,3]}，这样获得的总美味度为5+(-10)+15+(-1 0)+15+15=30，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为10。 8.Kiana取2次寿司，第一次取第1个寿司，第二次取第2个寿司，即她取寿司的情况为{[1,1],[2,2]}，这样获得的 总美味度为5+(-10)=-5，花费的总钱数为(1*2^2+1*2)+(1*3^2+1*3)=18，两者相减为-23； 9.Kiana取2次寿司，第一次取第1个寿司，第二次取第3个寿司，即她取寿司的情况为{[1,1],[3,3]}，这样获得的 总美味度为5+15=20，花费的总钱数为1*2^2+2*2=8，两者相减为12； 10.Kiana取2次寿司，第一次取第2个寿司，第二次取第3个寿司，即她取寿司的情况为{[2,2],[3,3]}，这样获得的 总美味度为(-10)+15=5，花费的总钱数为(1*2^2+1*2)+(1*3^2+1*3)=18，两者相减为-13； 11.Kiana取2次寿司，第一次取第1,2个寿司，第二次取第3个寿司，即她取寿司的情况为{[1,2],[3,3]}，这样获得 的总美味度为5+(-10)+(-10)+15=0，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为-20； 12.Kiana取2次寿司，第一次取第1个寿司，第二次取第2,3个寿司，即她取寿司的情况为{[1,1],[2,3]}，这样获得 的总美味度为5+(-10)+15+15=25，花费的总钱数为(1-22+2-2)+(1-32+1-3)=20，两者相减为5； 13.Kiana取2次寿司，第一次取第1,2个寿司，第二次取第2,3个寿司，即她取寿司的情况为{[1,2],[2,3]}，这样获 得的总美味度为5+(-10)+15+(-10)+15=15，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减为-5； 14.Kiana取3次寿司，第一次取第1个寿司，第二次取第2个寿司，第三次取第3个寿司，即她取寿司的情况为{[1,1] ,[2,2],[3,3]}，这样获得的总美味度为5+(-10)+15=10，花费的总钱数为(1*2^2+2*2)+(1*3^2+1*3)=20，两者相减 为-10。 所以Kiana会选择方案9，这时她获得的总美味度减去花费的总钱数的值最大为12。 HINT

Source

黑吉辽沪冀晋六省联考

这个优化建图没有yy出来菜了 如果按照yy的暴力建图复杂度大约1e8能过多少随缘

优化建图在于对于区间i,j那么只能向 (i,j-1)(i+1,j)建Inf即可 这样意味着选了i,j一定会选i,j-1,i+1,j

同理参照最大权闭合子图 只需要没个点都建下收益 如果是负的就往T建反之从S建

然后这个费用从结尾到a[i]连inf 然后a[i]向T连m*a[i]*a[i] 好了做完了

边数算错bzoj re一发 应该至少n^2*2这个量级的

#include#include#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int inf=0x3f3f3f3f;const int N=11000;bool flag[1100];struct node{ int y,next,z;}data[62000];int num=1,h[N],level[N],T,cnt,id[110][110],b[1100],a[110],n,m,cur[N],d[110][110];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].next=h[x];data[num].z=z;h[x]=num; data[++num].y=x;data[num].next=h[y];data[num].z=0;h[y]=num;}inline bool bfs(){ queueq;q.push(0);memset(level,0,sizeof(level));level[0]=1; while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[y]||!z) continue;level[y]=level[x]+1;if (y==T) return 1;q.push(y); } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int &i=cur[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(z,s));if (!xx)level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss; } }return ss-s;}int main(){ freopen("bzoj4873.in","r",stdin); n=read();m=read();int ans=0; for (int i=1;i<=n;++i) {a[i]=read();if (!b[a[i]]) b[a[i]]=++cnt;} for (int i=1;i<=n;++i) for (int j=i;j<=n;++j) d[i][j]=read(),id[i][j]=++cnt;T=cnt+1; for (int i=1;i<=n;++i) for (int j=i;j<=n;++j){ if (d[i][j]>0) insert1(0,id[i][j],d[i][j]),ans+=d[i][j]; if (d[i][j]<0) insert1(id[i][j],T,-d[i][j]); } for (int i=1;i<=n;++i) { insert1(id[i][i],T,a[i]);insert1(id[i][i],b[a[i]],inf); if(!flag[a[i]]&&m) insert1(b[a[i]],T,m*a[i]*a[i]),flag[a[i]]=1; }//printf("%d\n",ans); for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) insert1(id[i][j],id[i+1][j],inf), insert1(id[i][j],id[i][j-1],inf); while(bfs()) memcpy(cur,h,sizeof(cur)),ans-=dfs(0,inf); printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。