并不对劲的[noi2006]网络收费
这么长的题目告诉我们一定要学好政治。
听上去好像费用流，然而……
收费方式看上去很复杂，实际上没有想象中那么复杂但是也很复杂，可以看成A少就收所有的A，B少就收所有的B。这样用前缀和就能解决收费的问题了。
根据N<10大概猜到应该是状压dp，进而猜出dp(x,y,z)表示到第x个点，有y个A（或y个B），且祖先的取舍方案为z的收费情况。
那么问题就来了：用dp[x][y][z]表示的话，空间总共要占(2^10)^3!这样空间肯定会出问题。能不能将其中两维合成一维呢？
经过一番不对劲的思考，发现每往下走一层，z就会增加一位，而y的最大值会减少一半。把这两维放在同一维似乎不错。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#define maxm 5050
#define maxk 2050
using namespace std;
int dp[maxk][maxm],n,m,c[maxk],f[maxk][maxk];
int li[maxk],ri[maxk], ab[maxk];
int read()
{
int x=0,f=1;
char ch=getchar();
while(isdigit(ch)==0 && ch!='-')ch=getchar();
if(ch=='-')f=-1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int solve(int x,int y,int z,int l,int r,int lim)
{
li[x]=l,ri[x]=r;
int xi=x,xj=(z<<(lim+1))|y;
if(dp[xi][xj]!=-1)
{
return dp[xi][xj];
}
if(x>=m)
{
int tab,now=x-m+1,sum=c[now]*(ab[now]!=y),lu,ru;
for(int lstu=x,u=x>>1;u;lstu=u,u>>=1)
{
tab=z&1;
z>>=1;
lu=(lstu!=(u<<1))?li[u]:((li[u]+ri[u])>>1)+1;
ru=(lstu!=(u<<1))?((li[u]+ri[u])>>1):ri[u];
sum+=(f[now][ru]-f[now][lu-1])*(tab!=y);
}
dp[xi][xj]=sum;
return sum;
}
else
{
int tmp=(z<<1)|(y>(1<<lim)-y),res=0x7fffffff,mi=(l+r)>>1,siz=1<<(lim-1);
if(siz>y)siz=y;
for(int p=y-siz;p<=siz;p++)
{
int t=solve(x<<1,p,tmp,l,mi,lim-1)+solve((x<<1)+1,y-p,tmp,mi+1,r,lim-1);
res=min(res,t);
}
dp[xi][xj]=res;
return res;
}
}
int main()
{
//cout<<"Boy_next_door is playing game."<<endl;
n=read();
m=1<<n;
for(int i=1;i<=m;i++)
ab[i]=read();
for(int i=1;i<=m;i++)
c[i]=read();
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++)
{
f[i][j]=read();
f[j][i]=f[i][j];
}
memset(dp,-1,sizeof(dp));
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
f[i][j]=f[i][j-1]+f[i][j];
int ans=0x7fffffff;
for(int i=0;i<=m;i++)
{
int tmp1=solve(1,i,0,1,m,n);
ans=min(ans,tmp1);
}
cout<<ans;
return 0;
}