「vijos1891」学姐的逛街计划
描述
doc 最近太忙了, 每天都有课. 这不怕, doc 可以请假不去上课.
偏偏学校又有规定, 任意连续 n 天中, 不得请假超过 k 天.
doc 很忧伤, 因为他还要陪学姐去逛街呢.
后来, doc发现, 如果自己哪一天智商更高一些, 陪学姐逛街会得到更多的好感度.
现在 doc 决定做一个实验来验证自己的猜想, 他拜托 小岛 预测出了 自己 未来 3n 天中, 每一天的智商.
doc 希望在之后的 3n 天中选出一些日子来陪学姐逛街, 要求在不违反校规的情况下, 陪学姐逛街的日子自己智商的总和最大.
可是, 究竟这个和最大能是多少呢?
格式
输入格式
第一行给出两个整数, n 和 k, 表示我们需要设计之后 3n 天的逛街计划, 且任意连续 n 天中不能请假超过 k 天.
第二行给出 3n 个整数, 依次表示 doc 每一天的智商有多少. 所有数据均为64位无符号整数
输出格式
输出只有一个整数, 表示可以取到的最大智商和.
样例1
样例输入1
样例输出1
限制
对于 20% 的数据, 1 <= n <= 12 , k = 3.
对于 70% 的数据, 1 <= n <= 40 .
对于 100% 的数据, 1 <= n <= 200 , 1 <= k <= 10.
题解
设a[i]为第i天是否去逛街，v[i]为第i天智商
对于第i个不等式，添加辅助变量y[i]
设p[i]=a[i]+a[i+1]+…a[i+n-1]
则
a[1]+a[2]+…+a[n]+y[1]=k
a[2]+a[3]+…+a[n+1]+y[2]=k
…
a[2n+1]+a[2n+2]+…+a[3n]+y[2n+1]=k
ans=max{∑ a[i]*v[i]}
将相邻两式相减
得
a[1]+a[2]+…+a[n]+y[1]=k ———> 1
y[1]+a[1]=a[n+1]+y[2] ———> 2
y[2]+a[2]=a[n+2]+y[3] ———> 3
…
y[n+1]+a[n+1]=a[2n+1]+y[n+1] ———> n+1
…
y[2n]+a[2n]=a[3n]+y[2n+1] ———> 2n
a[2n+1]+a[2n+2]+…+a[3n]+y[2n+1]=k ———> 2n+1
然后把等式当做点，变量当做边
等号左右两边为流出/流入流量
最大费用最大流。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int n,K,T,cnt=1; ll a[605],d[605]; int q[605],last[605]; bool mark[605]; struct data{int to,next,v;ll c;}e[100005]; void ins(int u,int v,int w,ll c) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c; } void insert(int u,int v,int w,ll c) { ins(u,v,w,c); ins(v,u,0,-c); } void build() { for(int i=2;i<=n+1;i++)insert(1,i,1,a[i-1]); for(int i=n+2;i<=2*n+1;i++)insert(i-n,i,1,a[i-1]); for(int i=n+2;i<=2*n+1;i++)insert(i,2*n+2,1,a[i-1+n]); for(int i=2;i<=2*n+2;i++)insert(i-1,i,K,0); insert(0,1,K,0); insert(2*n+2,T,K,0); } bool spfa() { memset(mark,0,sizeof(mark)); for(int i=0;i<=T;i++)d[i]=-1; int head=0,tail=1; q[0]=T;mark[T]=1;d[T]=0; while(head!=tail) { int now=q[head];head++;if(head==605)head=0; for(int i=last[now];i;i=e[i].next) if(e[i^1].v&&d[now]+e[i^1].c>d[e[i].to]) { d[e[i].to]=d[now]+e[i^1].c; if(!mark[e[i].to]) { mark[e[i].to]=1; q[tail++]=e[i].to; if(tail==605)tail=0; } } mark[now]=0; } return d[0]!=-1; } int dfs(int x,int f) { mark[x]=1; if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(d[e[i].to]==d[x]-e[i].c&&e[i].v&&!mark[e[i].to]) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); ans+=w*e[i].c; e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { mark[T]=1; while(mark[T]) { memset(mark,0,sizeof(mark)); dfs(0,inf); } } } int main() { n=read();K=read();T=2*n+3; for(int i=1;i<=3*n;i++)a[i]=read(); build(); zkw(); printf("%lld",ans); return 0; } |
OI 课件=>
