挑戰(zhàn)程序設(shè)計競賽:抽簽-T數(shù)和(排序,二分查找,記憶化搜索)
//和書上答案不同,本解的n可以大一點,但m必須小。復(fù)雜度為O(n*m)。方法對幾個數(shù)字和是通用的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dim=4;
int k[1000];
int f[1000][1000][dim];
stack<int> si;
int solve(int n,int m,int dim,int level){
cout<<n<<" "<<m<<" "<<dim<<" "<<level<<endl;
level++;
if(f[n][m][dim]!=-1){
return f[n][m][dim];
}
if(n>=2 && m>=0 && dim>=0){
if(solve(n-1,m,dim,level)>=0){
f[n][m][dim]=1;
return 1;
}
}
if(n>=1 && m>=k[n] && dim>=1){
si.push(k[n]);
if(solve(n,m-k[n],dim-1,level)>=0){//放回口袋(數(shù)字可重用)
? ? ? ?//if(solve(n-1,m-k[n],dim-1,level)>=0){//不放回口袋(數(shù)字不可重用)
f[n][m][dim]=0;
return 0;
}
si.pop();
}
f[n][m][dim]=-2;
return -2;
}
int main(){
int n,m;
cin>>n>>m;
memset(f,-1,sizeof(f));
f[1][0][0]=0;
for(int i=1;i<=n;i++){
cin>>k[i];
}
if(solve(n,m,dim,0)>=0){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
while(si.size()>0){
cout<<si.top()<<" ";
si.pop();
}
cout<<endl;
return 0;
}