告诉你若干个（<=100）武器的花费以及武器能消灭的怪物编号，问消灭所有怪物(<=100)的最小花费。。。当然每个武器可以无限次使用，不然这题就太水了╮(╯▽╰)╭
这题当时比赛的时候连题都还没看就结束了。。。。赛后一看，果断是重复覆盖。。。
不过之后一直没敲。。。然后今天算是补回来吧，同时也把好久以前学的DLX复习一下。。。
DLX的话，双向十字链表。。。具体的话，百度Google什么的dancing links。。。
一开始敲的时候还是挺顺利的，因为之前做过几次重复覆盖都是直接拿精确覆盖的模板来改。。。差不多的，不过重复覆盖就删列，代码好像还少几行呢。。。不过有时调一会有时wa上一两发。。。又鉴于最近好像好多重复覆盖的题。。。就好像spfa一样频繁出现=。=个人感觉不科学。。。
而且之前那个精确覆盖的模板实在是无法直视，太挫了写得╮(╯▽╰)╭
重点来了~~~代码写好了，可是不AC╮(╯▽╰)╭太可恶了。。。。让JM帮忙看代码。。。于是苦逼地一直找bug。。。。
经过一小时吧大概的奋斗。。。JM发现。。。一个非常好笑的呵呵的亮点。。。。memset(vis,false,sizeof(false));。。。笑死我了。。。还好这是平时随便敲。。。
然后就AC了~~~
复杂度。。不知道怎么算DLX的复杂度哎~~~求高手教，或者说一般N,M多少可以~~
总结就是，打代码要仔细。。。。总之不要犯这种逗比错误。。。。真正比赛的时候就笑不出来了~~~啦啦啦~~~谢谢JM~~~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std; #define ll long long
#define eps 1e-8
#define mod 21092013 #define inf 0x3f3f3f3f
#define maxr 110
#define maxn (maxr*maxr)
int n,m;
int L[maxn],R[maxn],U[maxn],D[maxn],cnt;
int row[maxn],col[maxn];
int N[maxr],use[maxr],head[maxr];
void init(){
memset(head,-,sizeof(head));
memset(N,,sizeof(N));
for(int i=;i<=m;++i){
L[i]=i-,R[i]=i+;
U[i]=D[i]=i;
row[i]=,col[i]=i;
}
L[]=m,R[m]=;
cnt=m;
}
void remove(int x){// 删除列
for(int i=D[x];i!=x;i=D[i])
L[R[i]]=L[i],R[L[i]]=R[i];
}
void resume(int x){// 恢复列
for(int i=D[x];i!=x;i=D[i])
L[R[i]]=R[L[i]]=i;
}
int low(){
int mi=maxr,idx=;
for(int i=R[];i;i=R[i])if(N[i]<mi)mi=N[i],idx=i;
return idx;
}
void link(int r,int c){
++N[c],++cnt;
row[cnt]=r,col[cnt]=c;
U[cnt]=U[c],D[cnt]=c;
U[D[cnt]]=D[U[cnt]]=cnt;
if(head[r]==-)
head[r]=L[cnt]=R[cnt]=cnt;
else {
L[cnt]=L[head[r]];
R[cnt]=head[r];
L[R[cnt]]=R[L[cnt]]=cnt;
}
}
int cost[maxr];
int ans;
void dance(int dep,int val){
if(R[]==){
ans = min(ans,val);
return ;
}
int c=low();
if(c==||val>=ans)return ;
for(int i=D[c];i!=c;i=D[i]){
use[dep]=i;
remove(i);
for(int j=R[i];j!=i;j=R[j])remove(j);
dance(dep+,val+cost[row[i]]);
for(int j=L[i];j!=i;j=L[j])resume(j);
resume(i);
}
} int main(){
while(~scanf("%d%d",&m,&n)){
init();
bool vis[maxr];
memset(vis,false,sizeof(vis));
ans=;
for(int i=;i<=n;++i){
int tmp,tmp2;
scanf("%d%d",cost+i,&tmp);
ans+=cost[i];
for(int j=;j<tmp;++j){
scanf("%d",&tmp2);
vis[tmp2]=true;
link(i,tmp2);
}
}
for(int i=;i<=m;++i)if(vis[i]==false){vis[]=false;break;}
if(vis[]==false){puts("-1");continue;}
dance(,);
printf("%d\n",ans);
}
return ;
}
Note: 之后想起在cf上有一题类似的，当时用DLX重复覆盖超时了，要DP，然后再去试一下。。。
结果发现有一些数据会卡掉这份代码
在这里征求高手解答。。。。这种数据要怎么过。。。
我的想法是预处理weapon[i]能否完全代替weapon[j]或weapon[j]+weapon[k]...不过万一他要weapon[i]+weapon[j]才能完全代替weapon[k]+weapon[l]呢...好乱...
求高手解答....
void data(){
freopen("in.txt","w",stdout);
puts("33 99");
for(int i=;i<;++i)
if(i<)printf("%d %d %d\n",,,i%+);
else if(i<)printf("%d %d %d %d\n",,,i%+,(i+)%+);
else printf("%d %d %d %d %d\n",,,i%+,(i+)%+,(i+)%+);
}
参考了网上http://blog.sina.com.cn/s/blog_51cea4040100gwpv.html的剪枝优化。。。果然可以了。。。。可以跑出以上这种data了。。而且在fzu上的时间也从400+ms变成200+ms..排到第一了...有收获的感觉就是不错..这个剪枝感觉不错，好感动。。。泪牛满面，就是，当前价值+下界（不是下确界）>=best。。thank JM...
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std; #define ll long long
#define eps 1e-8
#define mod 21092013 #define inf 0x3f3f3f3f
#define maxr 110
#define maxn (maxr*maxr)
int n,m;
int L[maxn],R[maxn],U[maxn],D[maxn],cnt;
int row[maxn],col[maxn];
int N[maxr],use[maxr],head[maxr];
void init(){
memset(head,-,sizeof(head));
memset(N,,sizeof(N));
for(int i=;i<=m;++i){
L[i]=i-,R[i]=i+;
U[i]=D[i]=i;
row[i]=,col[i]=i;
}
L[]=m,R[m]=;
cnt=m;
}
void remove(int x){// 删除列
for(int i=D[x];i!=x;i=D[i])
L[R[i]]=L[i],R[L[i]]=R[i];
}
void resume(int x){// 恢复列
for(int i=D[x];i!=x;i=D[i])
L[R[i]]=R[L[i]]=i;
}
int low(){
int mi=maxr,idx=;
for(int i=R[];i;i=R[i])if(N[i]<mi)mi=N[i],idx=i;
return idx;
}
void link(int r,int c){
++N[c],++cnt;
row[cnt]=r,col[cnt]=c;
U[cnt]=U[c],D[cnt]=c;
U[D[cnt]]=D[U[cnt]]=cnt;
if(head[r]==-)
head[r]=L[cnt]=R[cnt]=cnt;
else {
L[cnt]=L[head[r]];
R[cnt]=head[r];
L[R[cnt]]=R[L[cnt]]=cnt;
}
}
int cost[maxr];
int best;
int micost[maxr];
int cost2(){// lower_bound
int ret=;
bool del[maxn];
memset(del,false,sizeof(del));
for(int c=R[];c;c=R[c]){
if(!del[c]){
del[c]=true;
ret+=micost[c];
for(int i=D[c];i!=c;i=D[i])
for(int j=R[i];j!=i;j=R[j])
del[col[j]]=true;
}
}
return ret;
}
void dance(int dep,int val){
if(R[]==){
best = min(best,val);
return ;
}
int c=low();
if(c==||val>=best)return ;
if(val+cost2()>=best)return ;// important!
for(int i=D[c];i!=c;i=D[i]){
use[dep]=i;
remove(i);
for(int j=R[i];j!=i;j=R[j])remove(j);
dance(dep+,val+cost[row[i]]);
for(int j=L[i];j!=i;j=L[j])resume(j);
resume(i);
}
} int main(){
//void data();data();return 0;
//freopen("in.txt","r",stdin);
while(~scanf("%d%d",&m,&n)){
init();
memset(micost,0x3f,sizeof(micost));
best=;
for(int i=;i<=n;++i){
int tmp,tmp2;
scanf("%d%d",cost+i,&tmp);
best+=cost[i];
for(int j=;j<tmp;++j){
scanf("%d",&tmp2);
link(i,tmp2);
micost[tmp2]=min(micost[tmp2],cost[i]);
}
}
for(int i=;i<=m;++i)if(!N[i]){N[]=;break;}
if(!N[]){puts("-1");continue;}
dance(,);
printf("%d\n",best);
}
return ;
}
void data(){
freopen("in.txt","w",stdout);
puts("20 100");
for(int i=;i<;++i)
printf("%d %d %d\n",,,i%+);
}
想着经过这样的优化，大概之前cf那题应该可以过吧（当时是TLE 42，然后用DP过的），改了一下，SUBMIT，AC。。。超级感动的说。。。虽然比DP的要慢，但毕竟是搜索算法嘛。。。很不错了。。。DLX 600+ms（只有第60个case>15ms....别的case都<=15ms）; DP 200+ms（相对较多100+ms,200+ms）。。。这篇应该不用再编辑了吧╮(╯▽╰)╭有错漏的话请观客提出=。=本人目前处于自嗨状态
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std; #define ll long long
#define eps 1e-8
#define mod 21092013 #define inf 0x3f3f3f3f
#define maxr 110
#define maxn (maxr*maxr)
int n,m;
int L[maxn],R[maxn],U[maxn],D[maxn],cnt;
int row[maxn],col[maxn];
int N[maxr],use[maxr],head[maxr];
int monitor[maxr];
int B;
void init(){
memset(head,-,sizeof(head));
memset(N,,sizeof(N));
for(int i=;i<=m;++i){
L[i]=i-,R[i]=i+;
U[i]=D[i]=i;
row[i]=,col[i]=i;
}
L[]=m,R[m]=;
cnt=m;
}
void remove(int x){// 删除列
for(int i=D[x];i!=x;i=D[i])
L[R[i]]=L[i],R[L[i]]=R[i];
}
void resume(int x){// 恢复列
for(int i=D[x];i!=x;i=D[i])
L[R[i]]=R[L[i]]=i;
}
int low(){
int mi=maxr,idx=;
for(int i=R[];i;i=R[i])if(N[i]<mi)mi=N[i],idx=i;
return idx;
}
void link(int r,int c){
++N[c],++cnt;
row[cnt]=r,col[cnt]=c;
U[cnt]=U[c],D[cnt]=c;
U[D[cnt]]=D[U[cnt]]=cnt;
if(head[r]==-)
head[r]=L[cnt]=R[cnt]=cnt;
else {
L[cnt]=L[head[r]];
R[cnt]=head[r];
L[R[cnt]]=R[L[cnt]]=cnt;
}
}
int cost[maxr];
ll best;
int micost[maxr];
ll cost2(){// lower_bound
ll ret=;
bool del[maxn];
memset(del,false,sizeof(del));
for(int c=R[];c;c=R[c]){
if(!del[c]){
del[c]=true;
ret+=micost[c];
for(int i=D[c];i!=c;i=D[i])
for(int j=R[i];j!=i;j=R[j])
del[col[j]]=true;
}
}
return ret;
}
void dance(int dep,ll val,int mak){
if(R[]==){
best = min(best,val+(ll)mak*B);
return ;
}
int c=low();
if(c==||val+(ll)mak*B>=best)return ;
if(val+(ll)mak*B+cost2()>=best)return ;// important!
for(int i=D[c];i!=c;i=D[i]){
use[dep]=i;
remove(i);
for(int j=R[i];j!=i;j=R[j])remove(j);
dance(dep+,val+cost[row[i]],max(mak,monitor[row[i]]));
for(int j=L[i];j!=i;j=L[j])resume(j);
resume(i);
}
} int main(){
//void data();data();return 0;
//freopen("in.txt","r",stdin);
while(~scanf("%d%d%d",&n,&m,&B)){
init();
memset(micost,0x3f,sizeof(micost));
best=;int mam=;
for(int i=;i<=n;++i){
int tmp,tmp2;
scanf("%d%d%d",cost+i,monitor+i,&tmp);
best+=cost[i];
mam=max(mam,monitor[i]);
for(int j=;j<tmp;++j){
scanf("%d",&tmp2);
link(i,tmp2);
micost[tmp2]=min(micost[tmp2],cost[i]);
}
}
best+=(ll)mam*B;
for(int i=;i<=m;++i)if(!N[i]){N[]=;break;}
if(!N[]){puts("-1");continue;}
dance(,,);
printf("%I64d\n",best);
}
return ;
}
void data(){
freopen("in.txt","w",stdout);
puts("20 100");
for(int i=;i<;++i)
printf("%d %d %d\n",,,i%+);
}
附上DP代码吧
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std; #define ll long long
//#define inf 0x3f3f3f3f
#define inf (1ll<<60)
#define maxn 110
#define mod 1000000007
#define eps 1e-8 struct node{
int x,k,st;
}p[maxn];
bool cmp(node a,node b){return a.k<b.k;}
ll dp[<<];
int main(){
int n,m,b,mm,tmp;
while(~scanf("%d%d%d",&n,&m,&b)){
for(int i=;i<n;++i){
scanf("%d%d%d",&p[i].x,&p[i].k,&mm);
p[i].st=;
while(mm--){
scanf("%d",&tmp);
p[i].st+=(<<(tmp-));
}
}
ll ans=inf;
sort(p,p+n,cmp);
for(int j=(<<m)-;j;--j)dp[j]=inf;
dp[]=;
for(int i=;i<n;++i){
for(int j=(<<m)-;j>=;--j)
dp[j|p[i].st] = min(dp[j|p[i].st], dp[j]+p[i].x);
ans = min(ans,dp[(<<m)-]+(ll)p[i].k*b);
}
if(ans==inf)puts("-1");
else printf("%I64d\n",ans);
}
return ;
}
FZU 2165 v11（最小重复覆盖）+ codeforces 417D Cunning Gena的更多相关文章
-
Codeforces 417D Cunning Gena(状态压缩dp)
题目链接:Codeforces 417D Cunning Gena 题目大意:n个小伙伴.m道题目,每一个监视器b花费,给出n个小伙伴的佣金,所须要的监视器数,以及能够完毕的题目序号. 注意,这里仅仅 ...
-
codeforces 417D. Cunning Gena 状压dp
题目链接 D. Cunning Gena time limit per test 1 second memory limit per test 256 megabytes input standard ...
-
FZU 1686 神龙的难题 （重复覆盖）
Problem 1686 神龙的难题 Accept: 397 Submit: 1258Time Limit: 1000 mSec Memory Limit : 32768 KB Prob ...
-
(简单) FZU 1686 神龙的难题 , DLX+可重复覆盖。
Description 这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,魔物也比较少.但是.总有一些魔物不时会进入城市附近,干扰人民的生活.就 ...
-
FZU2165 v11(带权的重复覆盖)
题意:有n个boss,m种武器,每种武器选用的时候需要有一定的花费ci,然后这个武器可以消灭掉其中一些BOSS,问你消灭完所有的BOSS,需要的最少花费是多少. 当时比赛的时候,看到这题以为是什么网络 ...
-
FZU Problem 1686 神龙的难题 重复覆盖
题目链接 给出大矩形的长宽, 矩形里面有1,0两个值, 给出小矩形的长宽, 求用最少的小矩形覆盖所有的1. 重复覆盖的模板题. #include <iostream> #include & ...
-
Codeforces 618D Hamiltonian Spanning Tree(树的最小路径覆盖)
题意:给出一张完全图,所有的边的边权都是 y,现在给出图的一个生成树,将生成树上的边的边权改为 x,求一条距离最短的哈密顿路径. 先考虑x>=y的情况,那么应该尽量不走生成树上的边,如果生成树上 ...
-
HDU 3957 Street Fighter （最小支配集 DLX 重复覆盖+精确覆盖 ）
DLX经典题型,被虐惨了…… 建一个2*N行3*N列的矩阵,行代表选择,列代表约束.前2*N列代表每个人的哪种状态,后N列保证每个人至多选一次. 显然对手可以被战胜多次(重复覆盖),每个角色至多选择一 ...
-
DLX 舞蹈链 精确覆盖 与 重复覆盖
精确覆盖问题:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得集合中每一列都恰好包含一个1 还有重复覆盖问题 dancing links 是 一种数据结构,用来优化搜索,不算是一种算法.(双向 ...
随机推荐
-
permission denied to create extension ";hstore";解决方案
首先 sudo -u postgres psql postgres 进入数据库后输入命令 ALTER USER mydb_user WITH SUPERUSER; (把某个用户设置为超级 ...
-
Extend Volume 操作 - 每天5分钟玩转 OpenStack（56）
前面我们讨论了 volume 的 attach 和 detach 操作,今天讨论如何扩大 volume 的容量.为了保护现有数据,cinder 不允许缩小 volume. Extend 操作用于扩大 ...
-
如何做好presentation
1.全心投入 要么不做,要做就做好 承诺自己会花时间好好准备自己的演讲,投入专注的精力. 人们可以通过练习使自己成为很好的演讲者. 2分析你的观众 他们想听什么? 3.组织你的想法 让语言简单 让观众 ...
-
hdu 1047 Integer Inquiry
题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1047 Integer Inquiry Description One of the first use ...
-
完全二叉树的高度为什么是对lgN向下取整
完全二叉树的高度为什么是对lgN向下取整呢? 说明一下这里的高度:只有根节点的树高度是0. 设一棵完全二叉树节点个数为N,高度为h.所以总节点个数N满足以下不等式: 1 + 21 + 22 +……+ ...
-
计算1到n整数中，字符ch出现的次数
个位ch个数 + 十位ch个数 * 10 + 百位ch个数 * 100:同时如果某一位刚好等于ch,还需要减去多算的一部分值. #include <stdio.h> //整数1到n,字符c ...
-
弹性布局详解——5个div让你学会弹性布局
前 言 JRedu 在网页制作过程中,布局是我们最重要的一个环节.可以说布局的好坏直接影响到整个网页的成败!布局成,则事半功倍:布局败,则事倍功半. 随着移动互联的到来,响应式网站风靡.这也就兴 ...
-
Python数据分析中 DataFrame axis=0(0轴)与axis=1(1轴)的理解
python中的axis究竟是如何定义的呢?他们究竟代表是DataFrame的行还是列? 直接上代码people=DataFrame(np.random.randn(5,5), columns=['a ...
-
day11 装饰器---函数的使用方法
这个是一个难点,以后面试会经常出现的,要搞懂! 装饰器升级版,进阶内容1: def outer(flag): def wrapper(func): def inner(*args,**kwargs): ...
-
英雄无敌HoMM3-死亡阴影SOD-神之苏醒WOG-封神NABI-MOD等相关文件
英雄无敌HoMM3:死亡阴影SOD 英雄无敌3之死亡阴影(Heroes of Might and Magic III: Shadow of Death,简记为HoMM III: SOD)发行于1999 ...