首页 > 代码库 > poj 3400 Dropping the stones
poj 3400 Dropping the stones
//next_permutation全排列 # include <stdio.h> # include <algorithm> # include <string.h> using namespace std; struct node { int w; int v; }; struct node a[10010]; int max1(int x,int y) { return x>y?x:y; } int main() { int i,n,d,flag,x1,y1,ans,max; int t[10010]; while(~scanf("%d%d",&n,&d)) { for(i=0;i<n;i++) { scanf("%d%d",&a[i].w,&a[i].v); t[i]=i; } max=0; do { flag=1; x1=0; y1=0; ans=0; for(i=0;i<n;i++) { if(flag) { x1+=a[t[i]].w; if(x1>y1+d) flag=0; } else { y1+=a[t[i]].w; ans+=a[t[i]].v; if(y1>x1+d) flag=1; } } max=max1(max,ans); }while(next_permutation(t,t+n)); printf("%d\n",max); } return 0; }
// dfs # include <stdio.h> # include <algorithm> # include <string.h> using namespace std; struct node { int w; int v; }; struct node a[10010]; int n,d,maxa; int vis[10010]; int max1(int x,int y) { return x>y?x:y; } void dfs(int w1,int w2,int v2,int ans,int flag) { if(ans==n) { maxa=max1(maxa,v2); return ; } else { for(int i=0;i<n;i++) { if(vis[i]==0) { vis[i]=1; if(flag&&w1>d+w2) { dfs(w1,w2+a[i].w,v2+a[i].v,ans+1,0); } else if(flag&&w1<=d+w2) { dfs(w1+a[i].w,w2,v2,ans+1,1); } else if(!flag&&w2>d+w1) { dfs(w1+a[i].w,w2,v2,ans+1,1); } else if(!flag&&w2<=d+w1) { dfs(w1,w2+a[i].w,v2+a[i].v,ans+1,0); } vis[i]=0; } } } return ; } int main() { while(~scanf("%d%d",&n,&d)) { for(int i=0;i<n;i++) { scanf("%d%d",&a[i].w,&a[i].v); } memset(vis,0,sizeof(vis)); maxa=0; dfs(0,0,0,0,1); printf("%d\n",maxa); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。