题解 P4941 【War2】

HiJ1m · 2018-10-27 21:28:40 · 题解

简单的状压DP，和NOIP2017 Day2 找宝藏 代码几乎一样。（比那个稍微简单一点）

f[i][j] ，i代表点的状态，j是当前选择的点，枚举上一个选到的点k 然后从f[i-(1<<(j-1))][k]转移到f[i][j]即可 方程f[i][j]=max(f[i][j],[k]+B[k][j]+A[j]);

注意的点1.开longlong 2.数据不保证X[i]和Y[i]都不同，也不保证X[i]不等于Y[i]，这里很坑要加特判。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int N,M,K;
long long f[1<<19][20],ans,A[20],B[400][400],a,b,c;
int count(int x){
    int c=0;
    while(x)c++,x&=(x-1);
    return c;
}
int main()
{
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=N;i++)scanf("%lld",&A[i]);
    for(int i=1;i<=K;i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a==b)A[a]+=c;
        B[a][b]+=c; 
    }
    for(int i=1;i<=N;i++)f[1<<(i-1)][i]=A[i];
    for(int i=1;i<=(1<<N)-1;i++){
        for(int j=1;j<=N;j++)
        if(i&(1<<(j-1))){
            for(int k=1;k<=N;k++)
            if(i&(1<<(k-1))&&j!=k){
                f[i][j]=max(f[i][j],f[i-(1<<(j-1))][k]+B[k][j]+A[j]);   
            }
            if(count(i)==M){
                for(int j=1;j<=N;j++)
                if(i&(1<<(j-1)))ans=max(ans,f[i][j]);   
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}       

Blog:Elfish.cnblogs.com