[链接] 我是链接, 点我呀:) [题意]
在这里输入题意
[题解]
写个 DP 设 f[j] 表示已经做的题的状态为 j 的情况下接着选能获得的最大分数. 显然是个倒推. 记忆化搜索一波 dfs(i,j) 表示当前选了 i 个题, 已选状态为 j. (当然这个 i 可以不用写. 因为可以看看 j 的二进制形式中 1 的个数来表示 i 然后枚举 j 状态下, 下一个要选哪个题. f[j] 的话. 就是 max({f[nextj]+dep*a[i]+b[i]} 当然也可能接下来就不选了. 所以 f[j] = max(f[j],0);
[代码]
- #include <bits/stdc++.h>
- #define LL long long
- #define rep1(i,a,b) for (int i = a;i <= b;i++)
- #define rep2(i,a,b) for (int i = a;i>= b;i--)
- #define all(x) x.begin(),x.end()
- #define pb push_back
- #define lson l,mid,rt<<1
- #define ri(x) scanf("%d",&x)
- #define rl(x) scanf("%lld",&x)
- #define rs(x) scanf("%s",x)
- #define rson mid+1,r,rt<<1|1
- using namespace std;
- const double pi = acos(-1);
- const int dx[4] = {0,0,1,-1};
- const int dy[4] = {1,-1,0,0};
- const int N = 20;
- int n;
- LL a[N+10],b[N+10];
- int statu[N+10];
- LL dp[(1<<20)+5];
- LL dfs(int dep,int status){
- if (dp[status]!=-1) return dp[status];
- LL ma = 0;
- rep1(i,1,n){
- int statu1 = status>>(i-1);
- statu1&=1;
- if (statu1>0) continue;
- statu1 = status&statu[i];
- if (statu1!=statu[i]) continue;
- statu1 = status|(1<<(i-1));
- ma = max(ma,dfs(dep+1,statu1)+1LL*a[i]*dep+b[i]);
- }
- return dp[status] = ma;
- }
- int main(){
- #ifdef LOCAL_DEFINE
- freopen("rush_in.txt", "r", stdin);
- #endif
- scanf("%d",&n);
- for (int i = 1;i <= n;i++){
- scanf("%lld%lld",&a[i],&b[i]);
- int x;
- scanf("%d",&x);
- rep1(j,1,x){
- int y;
- scanf("%d",&y);
- statu[i]|=(1<<(y-1));
- }
- }
- memset(dp,255,sizeof dp);
- printf("%lld\n",dfs(1,0));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2754987.html