首页 > 代码库 > Codeforces 294B Shaass and Bookshelf(记忆化搜索)
Codeforces 294B Shaass and Bookshelf(记忆化搜索)
题目
记忆化搜索(深搜+记录状态)
感谢JLGG
//记忆话搜索//一本书2中状态,竖着放或者横着放//初始先都竖着放,然后从左边往右边扫#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int dp[110][210][210];//dp[第几个][厚度][宽度]int n;int a[110],b[110];int rec(int i,int th,int w){ if(dp[i][th][w]!=-1)return dp[i][th][w]; int res; if(i==n)res=th; else if(th-a[i]<w+b[i])res=rec(i+1,th,w);//判断合不合法 else res=min(rec(i+1,th-a[i],w+b[i]),rec(i+1,th,w)); return dp[i][th][w]=res;}int main(){ while(scanf("%d",&n)!=EOF) { int th=0; for(int i=0;i<n;i++) { scanf("%d%d",&a[i],&b[i]); th+=a[i]; } memset(dp,-1,sizeof(dp)); int ans=rec(0,th,0); printf("%d\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。