CF 580 D,Kefa and Dishes(状圧DP)
1189 ワード
題意:n料理があり、各料理に1つの重み値があり、k条件があり、y料理目がx料理目の後すぐにcの付加価値があることを示す.そこからm料理を食べる最大の権利値を求めます.
この問題の詳細は以下の通りです.https://www.cnblogs.com/real-l/p/8597827.htmlまだ入門状圧DPにある萌新として,ここではDP状態をどのように出すかを分析する.まず、nの範囲は比較的小さく、各料理に食べない操作があり、バイナリ1,0で表すことができるので、DPを押すのは難しくない.次に、n料理は1<.最後に、料理の順番が違うと加算される可能性があるので、前回食べた最後の料理が何なのかを記録します.そこでDP状態差が少なく出てきた:状態:dp[i,j]は状態iの場合、最後の料理はjを食べるときに達成できる最大の重み値を表し、1<=i転移方程式:for(i.----for(j.----if(i&(1<(j-1))).for( k .----------------if ( ! ( i & ( 1<< (k-1) ) ) .---------------------dp[i|(1<
しかし、問題の意味には制限があるため、最終的にm料理を食べることになります.明らかに、DP状態にもう1次元を追加することはできません.それは大きすぎて、どのようにこの問題を解決するかはコードの中で体現されます.
この問題の詳細は以下の通りです.https://www.cnblogs.com/real-l/p/8597827.htmlまだ入門状圧DPにある萌新として,ここではDP状態をどのように出すかを分析する.まず、nの範囲は比較的小さく、各料理に食べない操作があり、バイナリ1,0で表すことができるので、DPを押すのは難しくない.次に、n料理は1<.最後に、料理の順番が違うと加算される可能性があるので、前回食べた最後の料理が何なのかを記録します.そこでDP状態差が少なく出てきた:状態:dp[i,j]は状態iの場合、最後の料理はjを食べるときに達成できる最大の重み値を表し、1<=i転移方程式:for(i.----for(j.----if(i&(1<(j-1))).for( k .----------------if ( ! ( i & ( 1<< (k-1) ) ) .---------------------dp[i|(1<
しかし、問題の意味には制限があるため、最終的にm料理を食べることになります.明らかに、DP状態にもう1次元を追加することはできません.それは大きすぎて、どのようにこの問題を解決するかはコードの中で体現されます.
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=1<<18;
ll dp[maxn][20];
ll a[20];
ll map[20][20];
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
memset(map,0,sizeof(map));
for(int i=1;i<=k;i++)
{
int x,y,c;
cin>>x>>y>>c;
map[x][y]=c;
}
memset(dp,0,sizeof(dp));
ll ans=0;
for(int i=1;i<=n;i++) dp[1<