div2 A题 Elimination
水题，但是很多人错，自己 也错了。后来重写，直接将所有的情况都写了，取最优值即可。不必分情况。
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const int MAXN = 1000010;
int n, m;
int c, d;
int k;
int main ()
{
RII(c, d);
RII(n, m);
RI(k);
if (k >= n * m)
{
puts("0");
return 0;
}
int ret = n * m - k;
int ans = min((ret + n - 1) / n * c, ret * d);
int x = ret / n;
int y = ret % n;
ans = min(ans, x * c + y * d);
printf("%d\n", ans);
return 0;
}
/*
4 3 51
100 1 1
1
100 1 1
2
1 4 1
2
200 4 1
3
*/状态压缩dp
其实分析清楚之后，当选定的monitor是定值得时候，就是一个重复区间覆盖，不过行有费用，求最小费用。
于是比赛时用DLX试了试，但最后还是TLE了。似乎当行比较少时，用这个方法比较好。而这个题的行为100，列100，点10000,。而且枚举monitor的值还要*100 。所以最后就超时了。
fzu的这道题，就可以用DLX，虽然我不是很清楚，但最后还是ac了。也可能是数据水了，表示对时间复杂度不是很清晰。
2014编程之美资格赛的第3题，感觉差不多。不知道行不行.??? 编程之美的那道题网上使用的网络流，待学习。。。
还有DLX本质就是搜索。。。只不过是加了剪枝优化而已。
然后本题的特征是目标状态比较少，只有20，所以可以状态压缩dp（最近总是不能直接想到。。。）
还有一点就是，本题中的monitor必须要在枚举完到达所有目标状态时在考虑 。也就是枚举到达目标状态的最小费用和这个状态的monitor。
总之，对于类似的题目，如果选择比较少是，考虑DLX搜索；如果目标状态比较少可以考虑状态压缩dp。
背包九讲中也曾提到搜索和dp的选择：物品数量比较少是选择搜索，状态数量比较少是选择dp
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const int MAXN = 1000010;
LL dp[2][1 << 20];
//int ttmm[2][1 << 20];
int ALL;
int now, next;
int n, m;
LL bi;
struct Node{
LL cost, ki;
vector<int> mv;
bool operator<(const Node &rhs) const
{
return ki < rhs.ki;
}
};
Node s[110];
int main ()
{
cin >> n >> m >> bi;
ALL = (1 << m) - 1;
for (int i = 0; i < n; i++)
{
int xn;
cin >> s[i].cost >> s[i].ki >> xn;
for (int j = 0; j < xn; j++)
{
int x;
scanf("%d", &x);
s[i].mv.push_back(x);
}
}
sort(s, s + n);
memset(dp[0], 0x3f, sizeof(dp[0]));
dp[0][0] = 0;
now = 0, next = 1;
LL ans = INF;
for (int i = 0; i < n; i++)
{
int xn = s[i].mv.size(), hv = 0;
for (int j = 0; j < xn; j++)
{
int x = s[i].mv[j];
hv |= (1 << (x - 1));
}
memset(dp[next], 0x3f, sizeof(dp[next]));
for (int r = 0; r <= ALL; r++)///ALL
{
if (dp[now][r] != INF)
{
dp[next][r] = min(dp[next][r], dp[now][r]);
int nextr = r | hv;
LL xx = dp[now][r] + s[i].cost;
dp[next][nextr] = min(dp[next][nextr], xx);
if (nextr == ALL) ans = min(ans, dp[next][ALL] + bi * s[i].ki);
}
}
// if (dp[next][ALL] != INF) ans = min(ans, dp[next][ALL] + bi * s[i].ki);///!!!
now ^= 1;
next ^= 1;
}
if (ans == INF) puts("-1");
else cout << ans << endl;
return 0;
}
/*
4 3 51
100 1 1
1
100 1 1
2
1 4 1
2
200 4 1
3
*/
cf RCC 2014 Warmup （D题 关于搜索和dp的选择的理解）,布布扣,bubuko.com
cf RCC 2014 Warmup （D题 关于搜索和dp的选择的理解）
原文：http://blog.csdn.net/guognib/article/details/24024745