首页 > 代码库 > POJ1160

POJ1160

2024-07-15 09:41:41   223人阅读

再次使用强大的四边形优化dp

f[i][j]=max(f[k][j-1]+w[k+1][i])

　　其中f[i][j]表示前i个村落有j个邮电局，w[i][j]表示[i,j]区间上安装一个邮电局最短路径和

其中w[i][j]邮电局必然是安装在(i+j)/2（中位数）的村落中，若(i+j)/2不为整数，则中间两个村落都可以。证明可以看《算法导论》

至于四边形不等式，这次，可以直接容易得到 s[i][j-1]<=s[i][j]<=s[i+1][j] 稍微证明下就可以出来，凭感觉都是对的。

 

#include <cstdio>#include <cstring>#define min(x,y) (x>y?y:x)int v,p,a[305],sum[305],w[305][305],f[305][35],s[305][35];int main(){    memset(f,127,sizeof(f));    scanf("%d%d",&v,&p);    for(int i=1; i<=v; i++){        scanf("%d",&a[i]);        sum[i]=a[i]+sum[i-1];    }    for(int i=1; i<=v; i++){        w[i][i]=0;        for(int j=i+1; j<=v; j++){            w[i][j]=sum[j]-sum[(i+j)/2]-sum[(i+j)/2-1]+sum[i-1];            if((i+j)%2!=0) w[i][j]-=a[(i+j)/2];        }    }    for(int i=1; i<=v; i++)        f[i][1]=w[1][i];    for(int j=2; j<=p; j++){        s[v+1][j]=v-1;        for(int i=v; i>=j; i--)        {            for(int k=s[i][j-1]; k<=s[i+1][j]; k++)            if(f[i][j]>f[k][j-1]+w[k+1][i])            {                f[i][j]=f[k][j-1]+w[k+1][i];                s[i][j]=k;            }        }    }    printf("%d",f[v][p]);    return 0;}

 


联系
我们