有n门课，给定每门课要花费的天数C和时限D，如果超过规定时间完成，每超过一天就会扣1分，问怎样安排做作业的顺序才能使得所扣的分最小
N<=15，可以用用状态压缩，最终状态1111111111111111111，即1《15-1
枚举所有状态i(1<=i<=totState)
对于第j门课，if(i&（1<<j）)说明状态i中有第j门课
那么i可以由状态i^(1<<j)而来
！！注意题目要求字典序，所以状态转移方程要取等号
dp[i]>=dp[lastState]+delay这是因为j是从1->n的，所以是1<<j递增的，则lastState递减，lastState小的应该优先
#include <stdio.h> #include <memory.h> const int maxn=105; const int maxs=1<<15+5; const int INF=0x777ffff; struct node { char S[maxn]; int D,C; }subjects[maxn]; int dp[maxs],time[maxs]; int pre[maxs]; void output(int s) { if(pre[s]==-1)return; output(pre[s]); int id=0; int tmp=pre[s]^s; tmp=tmp>>1; while(tmp){ id++; tmp=tmp>>1; } printf("%s\n",subjects[id].S); } int main() { //freopen("in.txt","r",stdin); int T,n; int tmp,lastState,delay; scanf("%d",&T); while(T--){ memset(pre,-1,sizeof(pre)); scanf("%d",&n); for(int i=0;i<n;i++)scanf("%s%d%d",subjects[i].S,&subjects[i].D,&subjects[i].C); int tot=1<<n; dp[0]=0; for(int i=1;i<tot;i++){ dp[i]=INF; for(int j=0;j<n;j++){ tmp=1<<j; if(i&tmp){ lastState=i^tmp; time[i]=time[lastState]+subjects[j].C; delay=time[i]-subjects[j].D; if(delay<0)delay=0; if(dp[i]>=dp[lastState]+delay){//注意大于等于号 dp[i]=dp[lastState]+delay; pre[i]=lastState; } } } } printf("%d\n",dp[tot-1]); output(tot-1); } return 0; }
