poj2248 真是个新套路。还有套路剪枝...大到小和判重
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<bitset> using namespace std;int n,D,x[110];bool bk,v[110][110]; void dfs(int k) {if(bk==true)return ;if(k==D+1)return ;if(x[k-1]>n)return ;if(x[k-1]==n){bk=true;for(int i=1;i<k-1;i++)printf("%d ",x[i]);printf("%d\n",x[k-1]);return ;}memset(v[k],false,sizeof(v[k]));for(int i=k-1;i>=1;i--){if(x[i]+x[i]<x[k-1])break;for(int j=i;j>=1;j--){if(x[i]+x[j]<x[k-1])break;if(v[k][x[i]+x[j]]==false){v[k][x[i]+x[j]]=true;x[k]=x[i]+x[j];dfs(k+1);x[k]=0;}}} } int main() {while(scanf("%d",&n)!=EOF){if(n==0)break;D=1;bk=false;x[1]=1;while(1){dfs(2);if(bk==true)break;D++;}}return 0; }
送礼物 折半搜索（orz cgh队长之前教我），书上叫双向搜索。又双叒叕有套路剪枝...大到小和很明显的可行性。结果dfs时居然还要先尝试选再尝试不选。。无语
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL;int n;int W,c[110]; bool cmp(int x,int y){return x>y;}int len;int a[10001000]; inline void dfs(int k,int d) {if(k==n/2+1){a[++len]=d;return ;}if(((LL)d)+c[k]<=W)dfs(k+1,d+c[k]);dfs(k+1,d); } int mmax; int erfen(int k) {int l=1,r=len;int ans;while(l<=r){int mid=(l+r)/2;if(a[mid]<=k){ans=a[mid];l=mid+1;}else r=mid-1;}return ans; } inline void dfs2(int k,int d) {if(k==n+1){mmax=max(mmax,d+erfen(W-d));return ;}if(((LL)d)+c[k]<=W)dfs2(k+1,d+c[k]);dfs2(k+1,d); } int main() {scanf("%d%d",&W,&n);for(int i=1;i<=n;i++)scanf("%d",&c[i]);sort(c+1,c+n+1,cmp);len=0;dfs(1,0);sort(a+1,a+len+1);len=unique(a+1,a+len+1)-a-1;mmax=a[len];dfs2(n/2+1,0);printf("%d\n",mmax);return 0; }#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL;int n;int W,c[110]; bool cmp(int x,int y){return x>y;}int len;int a[10001000]; inline void dfs(int k,int d) {if(k==n/2+1){a[++len]=d;return ;}if(((LL)d)+c[k]<=W)dfs(k+1,d+c[k]);dfs(k+1,d); } int mmax; int erfen(int k) {int l=1,r=len;int ans;while(l<=r){int mid=(l+r)/2;if(a[mid]<=k){ans=a[mid];l=mid+1;}else r=mid-1;}return ans; } inline void dfs2(int k,int d) {if(k==n+1){mmax=max(mmax,d+erfen(W-d));return ;}if(((LL)d)+c[k]<=W)dfs2(k+1,d+c[k]);dfs2(k+1,d); } int main() {scanf("%d%d",&W,&n);for(int i=1;i<=n;i++)scanf("%d",&c[i]);sort(c+1,c+n+1,cmp);len=0;dfs(1,0);sort(a+1,a+len+1);len=unique(a+1,a+len+1)-a-1;mmax=a[len];dfs2(n/2+1,0);printf("%d\n",mmax);return 0; }
