【洛谷4941】War2 状压Dp

时间：2023-01-17 20:24:51

简单的状压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[<<][],ans,A[],B[][],a,b,c;

int count(int x){

    int c=;

    while(x)c++,x&=(x-);

    return c;

}

int main()

{

    scanf("%d%d%d",&N,&M,&K);

    for(int i=;i<=N;i++)scanf("%lld",&A[i]);

    for(int i=;i<=K;i++){

        scanf("%lld%lld%lld",&a,&b,&c);

        if(a==b)A[a]+=c;

        B[a][b]+=c;

    }

    for(int i=;i<=N;i++)f[<<(i-)][i]=A[i];

    for(int i=;i<=(<<N)-;i++){

        for(int j=;j<=N;j++)

        if(i&(<<(j-))){

            for(int k=;k<=N;k++)

            if(i&(<<(k-))&&j!=k){

                f[i][j]=max(f[i][j],f[i-(<<(j-))][k]+B[k][j]+A[j]);

            }

            if(count(i)==M){

                for(int j=;j<=N;j++)

                if(i&(<<(j-)))ans=max(ans,f[i][j]);

            }

        }

    }

    cout<<ans<<endl;

    return ;

}

相关文章