ICPC 2018 南京网络预赛 E AC Chanllenge

【题目链接】

样例输入1
5
5 6 0
4 5 1 1
3 4 1 2
2 3 1 3
1 2 1 4
样例输出1
55
样例输入2
1
-100 0 0
样例输出2
0

Hint

在第一个样本中。

在第一分钟，dlsj提交了第一个问题，然后1乘以5+6=111×5+6=11积分。

在第二分钟，dlsj提交了第二个问题，2乘4+5=132×4+5=13积分。

在第三分钟，dlsj提交了第三个问题，3乘3+4=133×3+4=13积分。

在第四分钟，dlsj提交了第四个问题，4乘2+3=114×2+3=11积分。

在第五分钟，dlsj提交了第五个问题，5乘1+2=75×1+2=7积分。

这样他就能11+13+13+11+7=55总分。

在第二个示例中，您应该注意到，他不必解决所有问题。

解题思路

状压dp，因为n的范围是0-20，将所有状态压缩为一个数字，进行状态转移。

AC代码

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
using ll = long long;
ll dp[1 << 21], a[25], b[25], que[25];
int main()
{
    int n, t, tt;
    scanf("%d", &n);
    //将所有不是从0开始的状态设为-inf
    for (int i = 1; i < (1 << 21); i++)
        dp[i] = -LLONG_MAX;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld%lld%d", &a[i], &b[i], &t);
        while (t--)
        {
            scanf("%d", &tt);
            que[i] |= 1 << (tt - 1);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= (1 << n); i++)//枚举所有状态
    {
        for (int j = 0; j <= n; j++)//枚举所有问题
        {
            if (i&(1 << j))//如果状态i完成了第j题
            {
                int temp = i - (1 << j);//没完成第j个问题的状态
                if ((temp&que[j]) == que[j])//如果没完成第j个问题的状态满足可以完成第j个问题的条件
                {
                    int num = 1;
                    for (int k = 0; k <= 21; k++)
                        if (temp&(1 << k))
                            num++;//num是之前完成的题数
                    dp[i] = max(dp[i], dp[temp] + num * a[j] + b[j]);//状态转移
                    ans = max(ans, dp[i]);//取最大值
                }
            }
        }
    }
    printf("%lld\n", ans);
}