http://acm.hdu.edu.cn/showproblem.php?pid=1074
//1311853 2009-04-26 19:16:12 Accepted 1074 281MS 524K 1323 B C++ no way
#include<iostream>
#include<string>
using namespace std;
struct Node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
string course;
int deadline;
int need;
}infor[16];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int binary[16] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
int flag[65536];
bool mark[16];
string str[16],outs[16];
void dfs(int days,int cost,int sum,int num)//num表示选择的作业数
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { //days表示写作业的开始日期,cost表示前面的花费,sum记录作业是否完成情况
int i,temp;
if(num == n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(flag[sum] == cost)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
flag[sum] = cost;
for(i=0;i<num;i++)
outs[i] = str[i];
}
return ;
}
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(mark[i] == false)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mark[i] = true;
sum += binary[i];//要写第i门作业
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**////////////////////////////////////////////////////
temp = days + infor[i].need - infor[i].deadline;
if(temp < 0)
temp = cost;
else
temp += cost;
// 第i门作业完成后的代价 temp
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**///////////////////////////////////////
if(flag[sum] > temp)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
flag[sum] = temp; //记录状态
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
str[num++] = infor[i].course;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dfs(days + infor[i].need,temp,sum,num);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
num --;
}
sum -= binary[i];
mark[i] = false;
}
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t;
cin>>t;
while(t--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int i,st=0;
cin>>n;
for(i=1;i<=n;i++)
cin>>infor[i].course>>infor[i].deadline>>infor[i].need;
for(i=0;i<65536;i++)
flag[i] = 1000000;
memset(mark,false,sizeof(mark));//标记状态
dfs(0,0,0,0);
for(i=1;i<=n;i++)
st += binary[i]; //结果存放在下标为st的flag[st]值中
cout<<flag[st]<<endl;
for(i=0;i<n;i++)
cout<<outs[i]<<endl;
}
return 0;
}
|