Doing Homework HDU - 1074 題意： 有n個作業，每個作業有一個截止時間和完成所需時間，如果完成某個作業的時間超出了截止時間就扣完成時間-截止時間的分。求按怎樣的順序完成作業扣分最少。 方法：狀壓dp。ans[S]表示完成集合S的作業最少的扣分（集合S用一個數字表示）。pre[ ...
題意：
有n個作業，每個作業有一個截止時間和完成所需時間，如果完成某個作業的時間超出了截止時間就扣完成時間-截止時間的分。求按怎樣的順序完成作業扣分最少。
方法：狀壓dp。ans[S]表示完成集合S的作業最少的扣分（集合S用一個數字表示）。pre[S]和pre2[S]分別表示由前一個狀態到達狀態S完成的作業序號、S的前一個狀態。
首先應該意識到完成某個集合的作業，不管按照何順序，總時間都是一樣的。（曾經沒發現導致沒思路）
從小到大枚舉S（這樣的話枚舉到每個集合時其去掉某個作業得到的集合保證都已經枚舉到過，因為其子集的數字表示一定小於S）。
$ans[S]=min\{ans[S-p]+max(sumt[S]-d[p],0)\}$（p表示S集合內任意一項作業）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 typedef long long LL; 7 char name[16][110]; 8 LL d[16],c[16],ans[70000]; 9 LL pre[70000],pre2[70000]; 10 LL T,n,sumt; 11 vector<LL> vec; 12 int main() 13 { 14 LL i,j,t; 15 scanf("%lld",&T); 16 while(T--) 17 { 18 memset(name,0,sizeof(name)); 19 memset(ans,0x3f,sizeof(ans)); 20 memset(pre,0,sizeof(pre)); 21 memset(pre2,0,sizeof(pre2)); 22 scanf("%lld",&n); 23 for(i=1;i<=n;i++) 24 scanf("%s%lld%lld",name[i],&d[i],&c[i]); 25 ans[0]=0; 26 for(i=1;i<(1<<n);i++) 27 { 28 sumt=0; 29 for(j=1;j<=n;j++) 30 if(i&(1<<(j-1))) 31 sumt+=c[j]; 32 for(j=1;j<=n;j++) 33 if(i&(1<<(j-1))) 34 { 35 t=ans[i^(1<<(j-1))]+max(sumt-d[j],0LL); 36 if(t<=ans[i]) 37 { 38 ans[i]=t; 39 pre[i]=j; 40 pre2[i]=i^(1<<(j-1)); 41 } 42 } 43 } 44 printf("%lld\n",ans[(1<<n)-1]); 45 vec.clear(); 46 for(i=(1<<n)-1;i!=0;i=pre2[i]) 47 vec.push_back(pre[i]); 48 for(i=vec.size()-1;i>=0;i--) 49 printf("%s\n",name[vec[i]]); 50 } 51 return 0; 52 }
一個裸狀態壓縮~
題目大意: 一共有N門作業,三個數據是作業的名字,到期時間,和完成需要天數,完成做也期限超過一天扣一分.問以什麼順序完成作業可以使扣得分最少.如果有相同的分數名字按字典序排序.
狀態轉移方程: dp[i]=min(dp[j]+hw[k]-hwlast[k])+hw[k]; j為i中去掉第k個作業的狀態,hw[k]為當前作業需要幾天完成,hwlast為當前作業完成期限為多少,若(dp[j]+hw[k]<hwlast[k])則取零,表示狀態不可用.
源代碼:
#include <myhead.h>
const int N=16;
const int M=110;
const int NUM=(1<<N);
struct HomeWork {
char name[M];
int last;
int time;
};
struct Dp {
int timer;
int scr;
int last;
int i;
void init() {
this->timer=0;
this->scr=INT_MAX;
this->last=0;
this->i=0;
}
};
int n,num;
HomeWork hw[N];
Dp dp[NUM];
void init() {
scanf("%d",&n);
num=(1<<n);
dp[0].init();
dp[0].scr=0;
for(int i=0;i<n;++i) {
scanf("%s%d%d",hw[i].name,&hw[i].last,&hw[i].time);
}
}
void work() {
for(int i=1;i<num;++i) {
dp[i].init();
for(int j=n-1;j>=0;--j) {
int s=(1<<j);
if(s&i) {
int past=i-s;
int t=dp[past].timer+hw[j].time-hw[j].last;
checkmax(t,0);
t+=dp[past].scr;
if(t<dp[i].scr) {
dp[i].scr=t;
dp[i].i=j;
dp[i].last=past;
dp[i].timer=dp[past].timer+hw[j].time;
}
}
}
}
stack<int> s;
int star=num-1;
while(star) {
s.push(dp[star].i);
star=dp[star].last;
}
printf("%d\n",dp[num-1].scr);
while(!s.empty()) {
printf("%s\n",hw[s.top()].name);
s.pop();
}
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
init();
work();
}
return 0;
}
