[abc] Get Everything 状态压缩dp

前言 :

传送门 : 因为 n的范围很小 因此我们可以采用dp

思路

集合表示 : f [ i ] [ j ] f[i][j] f[i][j] 前 i i i把钥匙中,可以打开 j j j箱子的最小花费

因此不难想到状态转移 :

• 不选当前钥匙 f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j ] ) f[i][j] = max(f[i][j],f[i-1][j]) f[i][j]=max(f[i][j],f[i−1][j])
• 选当前钥匙 f [ i ] [ j ∣ b [ j ] ] = m a x ( f [ i ] [ j ∣ b [ j ] ] , f [ i − 1 ] [ j ] + a [ i ] ) f[i][j|b[j]] = max(f[i][j|b[j]],f[i-1][j]+a[i]) f[i][j∣b[j]]=max(f[i][j∣b[j]],f[i−1][j]+a[i])

特殊的 : 我们令 f [ 0 ] [ 0 ] = 0 f[0][0]=0 f[0][0]=0 其余的 都设置为正无穷

CODE

#include 
using namespace std;
#define int long long
#define ll long long
#define endl '\n'
const int maxn = 13,N = 1e3+10;
ll n,m,a[N],b[N];
ll dp[N][(1n>>m;
    for(int i=1;i>a[i];
        ll t;cin>>t;
        ll x =  0;

        for(int j=1;j>temp;
            x|=(1