「BZOJ1283」序列
Description
给出一个长度为 的正整数序列Ci，求一个子序列，使得原序列中任意长度为 的子串中被选出的元素不超过K(K,M<=100) 个，并且选出的元素之和最大。
Input
第1行三个数N,m,k。 接下来N行，每行一个字符串表示Ci。
Output
最大和。
Sample Input
10 5 3
4 4 4 6 6 6 6 6 4 4
4 4 4 6 6 6 6 6 4 4
Sample Output
30
HINT
20%的数据:n<=10。
100%的数据：N<=1000，k,m<=100。Ci<=20000。
题解
线性规划裸题
复习模板ing
题解请看：http://hzwer.com/4831.html与此题类似
本题式子大概是这样
b1 + b2 +…+ bm + y1 = K ————n+2
bm+1 + y2 = b1 + y1
bm+2 + y3 = b2 + y2
…
bn-m + yn-m+1 = bn + yn
bn-m+1 + … + bn + yn-m+1 = K ————–n+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 106 107 108 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 1000000007 using namespace std; int read() { int 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; } int n,m,cnt=1,K,T,ans; int a[2005],q[2005],last[2005],dis[2005]; bool inq[2005],mark[2005]; struct edge{ int to,next,v,c; }e[10005]; void insert(int u,int v,int w,int c) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;e[cnt].c=-c; } bool spfa() { int head=0,tail=1; memset(dis,-1,sizeof(dis)); q[0]=T;dis[T]=0; while(head!=tail) { int now=q[head];head++;inq[now]=0; if(head==2005)head=0; for(int i=last[now];i;i=e[i].next) if(dis[now]+e[i^1].c>dis[e[i].to]&&e[i^1].v) { dis[e[i].to]=dis[now]+e[i^1].c; if(!inq[e[i].to]) { inq[e[i].to]=1; q[tail++]=e[i].to; if(tail==2005)tail=0; } } } return dis[0]!=-1; } void build() { for(int i=1;i<=n;i++) { if(i<=m)insert(n+2,i,1,a[i]); else if(i<=n-m)insert(i-m,i,1,a[i]); else insert(i-m,n+1,1,a[i]); } for(int i=1;i<=n-m+1;i++) insert(i,i+1,K,0); insert(0,n+2,K,0); insert(n+1,T,K,0); } 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(!mark[e[i].to]&&e[i].v&&dis[x]-e[i].c==dis[e[i].to]) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; ans+=w*e[i].c; used+=w;if(used==f)return f; } return used; } void zkw() { int flow=0; while(spfa()) { memset(mark,0,sizeof(mark)); mark[T]=1; while(mark[T]) { mark[T]=0; flow+=dfs(0,inf); } } } int main() { n=read();m=read();K=read();T=n; for(int i=1;i<=n;i++)a[i]=read(); build(); zkw(); printf("%d\n",ans); return 0; } |
Subscribe
计数器 9327457
OI 课件=>
OI 课件=>