hdu1074 状态压缩dp+记录方案

题意：

给你一些作业，每个作业有自己的结束时间和花费时间，如果超过结束时间完成，一天扣一分，问你把n个作业完成最少的扣分，要求输出方案。

思路：

状态压缩dp，记录方案数的地方我用的是类似并查集的方法，记录当前状态是那个状态转移过来的，<输出的时候可以异或出来>，对于字典序最小，这个比较好处理，给的是升序的，所以直接更新的时候记录就行了，<如果没给可以sort下>，我是开了一个dp[i]表示i状态时的最小扣分，然后在开一个数组time[i]，记录dp[i]是对应的当前时间，然后每一个状态都用n个作业更新下，的到最优就行了，下面给出关键代码和ac代码

for(j = 0 ;j <= (1 << n) - 1 ;j ++)

for(i = 1 ;i <= n ;i ++)

{

int tt = time[j] + node[i].cost - node[i].end;

if(tt < 0) tt = 0;

if(dp[j|(1<<(i-1)))] > dp[j] + tt)

{

mer[j|(1<<(i-1))] = j;//记录路径

dp[j|(1<<(i-1))] = dp[j] + tt;

time[j|(1<<(i-1))] = time[j] + node[i].cost;

}

}

答案等于 dp[(1<<1)-1]

然后是输出路径

int x = (1 << n) - 1;

int id = 0;

while(x != mer[x])

{

Ans[++id] = x ^ mer[x];

x = mer[x];

}

for(i = n ;i >= 1 ;i --)

printf("%s\n" ,node[log2(Ans[i])+1].str);

#include<stdio.h>

#include<string.h>

#include<math.h>



typedef struct

{

   int end ,cost;

   char str[110];

}NODE;

NODE node[20];

int dp[1<<16];

int Time[1<<16];

int mer[1<<16];

int Ans[20];

int minn(int x ,int y)

{

   return x < y ? x : y;

}

int maxx(int x ,int y)

{

   return x > y ? x : y;

} 

int main ()

{

   int t ,n ,i ,j;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      for(i = 1 ;i <= n ;i ++)

      scanf("%s %d %d" ,node[i].str ,&node[i].end ,&node[i].cost);

      for(i = 0 ;i <= 1 << n ;i ++)

      dp[i] = 1000000000 ,Time[i] = 0 ,mer[i] = i;

      dp[0] = 0;

      for(j = 0 ;j <= (1 << n)-1 ;j ++)

      for(i = 1 ;i <= n ;i ++)

      {

         int tt = Time[j] + node[i].cost - node[i].end;

         if(tt < 0) tt = 0;

         if(dp[j|(1<<(i-1))] > dp[j] + tt)

         {

            mer[j|(1<<(i-1))] = j;

            dp[j|(1<<(i-1))] = dp[j] + tt;

            Time[j|(1<<(i-1))] =  Time[j] + node[i].cost;

         }

      }

      printf("%d\n" ,dp[(1<<n)-1]);

      int x = (1<<n) - 1;

      int id = 0;

      while(x != mer[x])

      {

         Ans[++id] = x ^ mer[x];

         x = mer[x];

      }

      for(i = n ;i >= 1 ;i --)

      printf("%s\n" ,node[int(log2(Ans[i]))+1].str);

   }

   return 0;

}

巴特西

hdu1074 状态压缩dp+记录方案

最新文章

热门文章