题意与分析（CodeForces 580D）

一个人有\(n\)道菜，然后要点\(m\)道菜，每道菜有一个美味程度；然后给你了很多个关系，表示如果\(x\)刚好在\(y\)前面做的话，他的美味程度就会增加\(c\)。求最大的美味程度。

这种题目一看就是状压dp，\(n \le 15\)啊。定义\(dp[i][stat]\)等于最后一道菜为第i个菜，吃完第i道菜后的状态是stat（第i位为是否吃过，二进制位数的和是吃过菜的总数）的最大美味程度。那么$$dp[i][stat]=max{dp[j][stat-(1<<(i-1))]+extra[j][i]+taste[i]}$$其中i、j必须在stat中有。然后记忆化搜索或者递推去解都可以。可以说是状压dp的板子题了。注意一下边界条件和起始求值即可。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB emplace_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (repType i = (a); i <= (b); ++i)

#define per(i, a, b) for (repType i = (a); i >= (b); --i)

#define MS(x,y) memset(x,y,sizeof(x))

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll=long long;

using repType=ll;

ll dp[25][1000005];

ll taste[25];

ll extra[25][25];

int n,m,k;

ll solve(int last, int stat) // stat after eating up last

{

	//cout<<last<<" "<<stat<<endl;

	if(dp[last][stat]!=-1) return dp[last][stat];

	else

	{

		ll ans=0;

		int val=(stat-(1<<(last-1)));

		rep(i,1,n)

		{

			if(val&(1<<(i-1)))

			{

				ans=max(ans,solve(i,val)+extra[i][last]+taste[last]);

			}

		}

		//cout<<"    "<<last<<": "<<stat<<" "<<ans<<endl;

		return dp[last][stat]=ans;

	}

}

int main()

{

	MS(dp,-1);

	cin>>n>>m>>k;

	rep(i,1,n)

	{

		cin>>taste[i];

		dp[i][1<<(i-1)]=taste[i];

	}

	/*

	rep(i,1,n)

	{

		rep(j,0,((1<<n)-1))

			cout<<dp[i][j]<<" ";

		cout<<endl;

	}

	*/

	rep(i,1,k)

	{

		int x,y,c;

		cin>>x>>y>>c;

		extra[x][y]=c;

	}

	ll ans=0;

	rep(i,1,n) dp[i][(1<<n)-1]=solve(i,(1<<n)-1);

	rep(i,1,n)

	{

		rep(j,0,((1<<n)-1))

		{

			if(__builtin_popcount(j)==m)

			{

				ans=max(ans,dp[i][j]);

			}

			//cout<<dp[i][j]<<" ";

		}

		//cout<<endl;

	}

	cout<<ans<<endl;

}