vijosP1159 岳麓山上打水

vijosP1159 岳麓山上打水

链接:https://vijos.org/p/1159

【思路】

迭代加深搜索+完全背包判断。

自己没有思路,看的别人代码。

总体上讲就是不断增大桶的数目并以之为上界搜索,用DP判断搜索是否可行。貌似数据很水所以可以较快通过。

其中DFSID(cur+1,dep)很奇妙,如果改成取i从0到n的搜索的话会TLE。

【代码】

 #include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std; const int maxn = +; int dp[];
int ans[maxn],a[maxn];
int n,q,max_d; int check(int sum)
{
int &cur=dp[sum];
if(cur != -) return cur;
if(sum==) return cur=;
else
{
for(int i=;i<max_d;i++)
if(sum>=ans[i] && check(sum-ans[i]))
return cur=;
}
return cur=;
} void DFSID(int cur,int dep) {
if(dep==max_d) //到达深度限制判断是否能够组成q
{
memset(dp,-,sizeof(dp));
if(check(q))
{
cout<<max_d<<" ";
for(int i=;i<dep;i++) cout<<ans[i]<<" ";
exit();
}
return ; //return
} if(cur>=n) return ; ans[dep]=a[cur];
DFSID(cur+,dep+);
DFSID(cur+,dep); //一个不错的写法
} int main() {
ios::sync_with_stdio(false); cin>>q>>n;
for(int i=;i<n;i++) cin>>a[i]; sort(a,a+n); //字典序要求最小 for(max_d=;max_d<=n;max_d++)
DFSID(,); return ;
}
上一篇:iOS-JS交互 (WebViewJavascriptBridge)


下一篇:短视频平台源码,短视频平台面临的内容危机