Doing Homework [kuangbin带你飞]刷题记录

Doing Homework

题目链接

核心思想:

状压dp
我们将做完的作业弄成一个集合 , 比如是[1,2,4]
那么最后做完集合[1,2,3,4,]=max{ ( [2,3,4]+最后做1 ) , ( [1,3,4]+最后做2 ) , ( [1,2,4]+最后做3 ) ( [1,2,3]+最后做4 )}
同理每个集合的最优状态一定是上一个状态最优解分+最后做的这个元素的分
用2机制存转态进行转移即可
我的代码dp[x]=y表示 : 做完集合x里的作业最小分数为y

AC代码

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define intxt freopen("in.txt","r",stdin)
#define CAS int cas;cin>>cas;while(cas--)
#define py  puts("Yes")
#define pn  puts("No")
#define pcn  putchar('\n')
inline int read( ) {int f = 1,x = 0;char ch = getchar();while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}x *= f;return x;
}
const int maxn=1e6+5;int n;
string name[20];
int deadday[20],cost[20];
int dp[40000];
int tianshu[40000];
struct cpp{int bw;int pre;
}path[40000];//32,768
int main(){//intxt;CAS{n=read();repi(i,1,32767){dp[i]=1e9;tianshu[i]=0;path[i].bw=0;path[i].pre=0;}repi(i,1,n){cin>>name[i]>>deadday[i]>>cost[i];}int v = (1<<n) - 1;//cout<<v<<endl;int val,now;repi( k,1,n ){repi(i,1,n){repi(j,0,v){if( ( (1<<(i-1))& j )==0 ){//如果该点 i 不在集合j里now = (1<<(i-1)) | j ;//将 i 放入 j 中的新集合val = tianshu[ j ] + cost[i] -deadday[i];if(val<0) val=0;if( dp[j]+max(val,0) <= dp[ now ] ){//字典序最小 , 我是顺序遍历的,所以要取=tianshu[ now ] = tianshu[ j ] + cost[i];dp[ now ] = dp[j]+val;path[ now ].bw = i ;path[ now ].pre = j ;}}}}}cout<<dp[v]<<endl;stack<int> cup;repi(i,0,n-1){cup.push( path[ v ].bw );v=path[v].pre;}while(!cup.empty()){cout<<name[ cup.top() ]<<endl;cup.pop();}}return 0;
}