首页 > 代码库 > 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;}
View Code