二十天之前寫的題，現(xiàn)在完全不記得思路了。
碰見dp題宕機不說，還瞎指鹿為馬，氣煞我也，一個期中考試回到解放前。
所以回來吃掉你了

題目鏈接：
https://www.acoj.com/problems/12098

AC代碼：

#include<stdio.h>       
#include<string.h>
int n,m;                                        //m個人參與挖礦，共n座礦
int A[105],B[105],dp[105][1005];                //A表示該礦挖掘需要人數(shù),B表示該礦可得金子數(shù) 

int max(int a,int b)
{
    return a>b?a:b; 
} 

int f(int i,int j)                              //i是第i座金礦,j是該礦可得金子數(shù)
{
    int ans;
    if(dp[i][j]!=-1)
        return dp[i][j];                            //dp記憶化搜索 
        
    if(i==n)
        ans=0;          //return 0; 
    
    else if(A[i]>j)
        ans=f(i+1,j);
    else
        ans=max(f(i+1,j),f(i+1,j-A[i])+B[i]);       //max(dp[i+1][j],dp[i+1][j-A[i]]+B[i]);
    
    dp[i][j]=ans;                               //dp記憶化搜索 
    return ans; 
} 

int main()
{
    scanf("%d%d",&m,&n);
    
    memset(dp,-1,sizeof(dp)); 
    for(int i=0;i<n;i++) 
        scanf("%d%d",&A[i],&B[i]); 
    
    printf("%d",f(0,m));
}