本文共 2487 字，大约阅读时间需要 8 分钟。
【题目】
【题解】
这道题是01背包的模板题。
普通搜索的复杂度过高，因为存在大量重复计算，而记忆化搜索能有效处理重叠子问题。记忆化搜索是在搜索过程中，通过记录一些状态的答案，从而减少重复搜索的计算量 。
简单来说，记忆化搜索=搜索的形式+动态规划的思想。
【记忆化搜索】
#include #define maxn 105using namespace std;int t,m;int w[maxn],v[maxn];int dp[maxn][maxn*10]; //记忆数组int dfs(int i,int j) //从第i个物品挑选总重小于j的部分 { if(dp[i][j]>=0) return dp[i][j]; //遍历过的情况直接返回 int res; if(i==m) res=0; //选完了 else if(j
【dp】
#include using namespace std; main() { int t,m,w[105],v[105]; int dp[1005]; scanf("%d%d",&t,&m); memset(dp,0,sizeof(dp)); for(int i=0;i =w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); printf("%d",dp[t]); }
【题目】
【题解】
法一：记忆化搜索暴搜加剪枝。
法二：普通暴力搜索会超时，考虑优化减少不必要的搜索。用贪心的思想，普通17m/s比较优时优先使用普通速度，1s60m加上魔法值加到10所需要的时间的总时间少于使用普通速度时，使用闪烁法术。
【记忆化搜索】
#include #define maxn 101#define inf 0x3f3f3f3fusing namespace std;int m,s,t;int dp[300005][15];void dfs(int pos,int sumM,int sumT){ if(sumT>t) return; if(dp[sumT][sumM]>=pos) return; //若之前记录的状态更优就没有继续搜索的必要了 else dp[sumT][sumM]=pos; if(pos>=s) return; if(sumM>=10) dfs(pos+60,sumM-10,sumT+1); else { dfs(pos,sumM+4,sumT+1); dfs(pos+17,sumM,sumT+1); }}int main(){ memset(dp,-1,sizeof(dp)); scanf("%d%d%d",&m,&s,&t); int dis=0,ti=0; while(dis =10&&ti =s) printf("Yes\n%d",ti); else if(ti==t) printf("No\n%d",dis); else { dfs(dis,m,ti); int ans=0; for(int i=ti;i<=t;i++) for(int j=0;j<14;j++) { ans=max(ans,dp[i][j]); if(ans>=s) { printf("Yes\n%d",i); return 0; } } printf("No\n%d",ans); } return 0;}
【贪心】
#include #define maxn 101#define inf 0x3f3f3f3fusing namespace std;int m,s,t,f=0;int dis=0,ti=inf;void dfs(int pos,int sumM,int sumT){ if(pos>=s) { f=1; ti=min(ti,sumT); return; } if(sumT==t) { dis=max(dis,pos); return; } int d=s-pos; if(sumM>=10&&d>17) dfs(pos+60,sumM-10,sumT+1); else if(sumM<10&&sumM>=6&&d>34&&sumT+2<=t) dfs(pos+60,sumM-6,sumT+2); else if(sumM<10&&sumM>=2&&d>51&&sumT+3<=t) dfs(pos+60,sumM-2,sumT+3); else if(sumM<2&&d>68&&sumT+4<=t) dfs(pos+60,sumM+2,sumT+4); else dfs(pos+17,sumM,sumT+1);}int main(){ scanf("%d%d%d",&m,&s,&t); dfs(0,m,0); if(f) printf("Yes\n%d",ti); else printf("No\n%d",dis); return 0;}
转载地址：http://wbben.baihongyu.com/