关于记忆化搜索

#include<iostream>
#include<cstring>
#include<string>
const int inf=1e9;
const int maxn=1e4+5;
using namespace std;
int n,m,k,ans=inf,fow;
int up[maxn],dn[maxn],l[maxn],h[maxn];
int f[10005][1055];
int dfs(int dep,int hig,int sum)
{
    if(sum>ans)return inf;    
    if(hig>=h[dep]||hig<=l[dep]||hig==0||hig<0)return inf;    
//    printf("%d %d\n ",dep,hig);
    fow=max(fow,dep);
    if(dep==n)return f[dep][hig]=sum;
    if(f[dep][hig]!=-1)return f[dep][hig];
    int tmp=inf;
    tmp=min(tmp,dfs(dep+1,hig-dn[dep],sum));
    for(int i=1;i<=inf;i++)
    {
        tmp=min(tmp,dfs(dep+1,min(hig+up[dep]*i,m),sum+i));
        if(hig+up[dep]*i>min(h[dep+1],m))break;
    }    
    return f[dep][hig]=tmp;

}
int main()
{
    freopen("P1941_4.in","r",stdin);
    memset(f,-1,sizeof(f));
    scanf("%d %d %d ",&n,&m,&k);
    for(int i=0;i<n;i++)
        scanf("%d %d",&up[i],&dn[i]);
    for(int i=0;i<=n;i++)h[i]=inf;
    for(int i=1,p;i<=k;i++)
    {
        scanf("%d ",&p);
        scanf("%d %d",&l[p],&h[p]);
    }
        
    for(int i=0;i<=m;i++)
        ans=min(ans,dfs(0,i,0));
    if(ans==inf)
    {
        puts("0");
        ans=0;
        for(int i=0;i<=fow;i++) 
            if(h[i]!=inf)
                ans++;
        printf("%d\n",ans);
        return 0;
    }
    printf("%d\n%d\n",1,ans);
    return 0;
}