最小AC爆零流

rp+=INF!(

集训day8t1 梦工厂

tql

tym983398371:









只写了60分的暴力,斜率优化还没来得及写,题解等我把100分的写了再补吧。。




60分


#include<iostream>


#include<algorithm>


#include<cstdio>


#include<cstring>


#include<vector>


#include<map>


using namespace std;


int n,m,a[100005],b[100005],f[100005];


long long cime;


inline 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;


}




void fan2()


{


int x;


int ans[15][15];


memset(ans,0,sizeof(ans)); 


for (int i=1;i<=n;i++) f[i]=read();


for (int i=1;i<=10;i++)


{


for (int j=1;j<=n;j++) a[j]=i*f[j];


for (int j=1;j<=10;j++)


{


for (int k=1;k<=n;k++) b[k]=j*f[k];


long long ans1=0;


for (int k=1;k<n;k++) 


{


ans1+=a[k+1]-b[k];


if (ans1>0) ans[i][j]+=ans1,ans1=0;


}


}


}


x=read();


int y;


for (int i=2;i<=m;i++)


{


y=x;


cime+=y*f[1];


x=read();


cime+=ans[y][x];


}


for (int i=1;i<=n;i++) cime+=f[i]*x;


printf("%lld\n",cime);


return ;


}




int main()


{


freopen("yume.in","r",stdin);


freopen("yume.out","w",stdout);


cime=0;


n=read();m=read();


if (n>1000) 


{


fan2();


return 0;


}


for (int i=1;i<=n;i++) scanf("%d",&f[i]);


int x;


x=read();


for (int i=1;i<=n;i++) a[i]=x*f[i];


for (int i=2;i<=m;i++)


{


cime+=a[1];


x=read();


for (int j=1;j<=n;j++) b[j]=x*f[j];


long long ans1=0,ans2=0;


for (int j=1;j<n;j++) 


{


ans1+=a[j+1]-b[j];


if (ans1>0) ans2+=ans1,ans1=0;


}


//for (int j=1;j<n-1;j++) ans2+=max(b[j]-a[j+1],)


cime+=ans2;


for (int j=1;j<=n;j++) a[j]=b[j];


}


for (int i=1;i<=n;i++) cime+=a[i];


printf("%lld\n",cime);


return 0;


}



评论

热度(2)

  1. 最小AC爆零流tym983398371 转载了此文字
    tql