hdoj1074【A的无比爆炸】-白红宇

hdoj1074【A的无比爆炸】

阅读量：4704 次

发布时间：2019-06-10

本文共 1468 字，大约阅读时间需要 4 分钟。

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊，一开始我就不知道怎么写，然后看了题解是状压DP，后来去看了看状压DP也就这样嘛，但是难点，可以说是不熟悉的地方吧。。。如下：

第一、我们能很快的知道状压DP的原理：

就比如我们要考虑一些状态的时候，比如做这题做作业，有N[0 , 15]个作业，我们要表示1,2,3,….,n个作业的状态，我们可以用1/0来表示作业的状态是做完或者没做完。1101 :1号做完，3号做完，4号做完，加入我们开一个数组，当然1e15大的数组也不行，当然如果N再小一点，我们硬要去用数组存起来，那么那些156，8494这样的下标就变得没有意义。所以，我们可以利用二进制用13的二进制1101代表:1号做完，3号做完，4号做完作业。

这样的我们就叫做，状态压缩

第二、其实第一很好理解的，但是难点就是状态的转化，后来还是很简单，判断一下就好了，任何超出的时间代表扣的分数，每次用中间值temp=前面的扣分+当前扣分，如果这种状态访问过了，比较当前扣分，取小

第三、也是最不熟悉的，位运算，一个是按位或，一个状态下，如果该状态没有该作业，用cur | j 加进去。所以还有就是按位异或，

采用异或运算，相同的就会消去，留下的值的二进制就是某个作业的二进制

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long LL;#define INF 0x3f3f3f3f#define PI acos(-1.0)const int N=1<<16;struct asd{ int cost; int pre; //记录前一状态，记录路径。 int reduce;}dp[N];bool vis[N];struct cd{ int die; int cost; char name[150];}cou[19];void outt(int x){ int curjob=dp[x].pre^x; //采用异或运算，相同的就会消去，留下的值的二进制就是某个作业的二进制 int curid=0; curjob>>=1; while(curjob) //右移，得出第几个作业。 { curid++; curjob>>=1; } if(dp[x].pre!=0) { outt(dp[x].pre); } printf("%s\n",cou[curid].name);}int main(){ int n,i,j; int t; cin>>t; while(t--) { scanf("%d",&n); int upp=1<
              
               j){ dp[curtemp].pre=j; } } } else{ vis[curtemp]=1; dp[curtemp].pre=j; dp[curtemp].reduce=reduce; } } } } printf("%d\n",dp[tup].reduce); outt(tup); } return 0;}

转载于:https://www.cnblogs.com/keyboarder-zsq/p/5934459.html

你可能感兴趣的文章