CF580D Kefa and Dishes [洛谷]
题目传送门
一、题目大意
\(kefa\)进入了一家餐厅,这家餐厅中有\(n\)个菜(\(0
输入第一行是三个数:\(n,m,k\)
第二行是\(n\)个数,第\(i\)个数表示\(kefa\)对第\(i\)道菜的满意度为\(a_i\)
第三行到第\(k+2\)行每行有\(3\)个数:\(x_i,y_i,c_i\),表示如果\(kefa\)在吃完第\(x_i\)道菜之后立刻吃了第\(y_i\)道菜,则会额外获得\(c_i\)的满意度
输入#1
2 2 1
1 1
2 1 1
输出#1
输入 #2
4 3 2
1 2 3 4
2 1 5
3 4 2
输出 #2
12
二、题目分析
翻译的人还好心的告诉我们要用状压。。。,其实看看数据范围也可以证明这一点,\(n<=18\)。而且"XXX"最大之流,看着就像是动态规划吧!
这题在一般状压的基础上加了一点变化:状态之间有联系,其实也是废话,状态之间没有冲突,没有关联,还用你来做题吗?
题目中说:这\(n\)个菜有\(k\)个规则,如果\(kefa\)在吃完第\(x_i\)个菜之后吃了第\(y_i\)个菜(保证\(x_i、y_i\)不相等),那么会额外获得\(c_i\) (\(0<=c_i<=10^9\))的满意度。
显然这是与吃菜的顺序有关的
但是再仔细考虑一下,会发现其实也是没有后效性的
因为一道菜只与它前面的那道菜有关
显然我们可以枚举要吃的菜的前面那道菜
不妨设状态\(f[i][j]\)表示当状态为\(i\)时,最后吃的一道菜为\(j\)时获得的最大满意度
-
当前状态\(i\) : \(f[i]\)
-
当前状态\(i\)包含\(j\)这道菜,且前序状态不包含\(j\)
因为\(i\)需要包含了\(j\)这道菜,即\(i\)的第\(j\)位置必须是\(1\)
前序状态不能包含\(j\)这道菜,即前序状态的第\(j\)位置需要是\(0\)
也就是:\(f[i\)^\((1<
可行的状态有转移方程:
\(f[i][j]=max(f[i\)^\((1<
显然当那些状态中存在\(m\)个\(1\)时(已经吃了\(m\)道菜)取\(max\)即为最后的答案
三、完整代码
#include
using namespace std;
typedef long long LL;
const int N = 20;
int a[N], c[N][N];
int K;
int n, m;
LL f[1 << N][N], ans;
//统计某个状态中数字1的数量
int count(int x) {
int res = 0;
for (int i = 0; i < 32; i++) res += x >> i & 1;
return res;
}
int main() {
cin >> n >> m >> K;
for (int i = 0; i < n; i++) { //下标从0开始
cin >> a[i];
f[1 << i][i] = a[i]; //只吃一个的初始化
}
while (K--) {
int x, y, w;
cin >> x >> y >> w;
x--, y--; //状态压缩的套路
c[x][y] = w; //记录x,y的前后关联关系
}
for (int i = 0; i < (1 << n); i++) { //枚举所有状态
for (int j = 0; j < n; j++) { //枚举每一位
if ((i & (1 << j)) == 0) continue; //不包含j的不是本次要计算的状态
for (int k = 0; k < n; k++) { //枚举前一次最后一个菜k,看看会不会获取到更大的满意度
/*
1、本轮吃下j,最后形成i这样的状态,那么上轮没有j,状态为 i^(1<