动态规划与记忆化搜索

kaiyuan · 2019-09-28 15:23:50 · 个人记录

引入

采药（luogu P1048）

题解

直接写一个粗暴的 DFS :

int n,t;
int tcost[103],mget[103];
int ans = 0;
void dfs( int pos , int tleft , int tans ){
    if( tleft < 0 ) return;
    if( pos == n+1 ){
        ans = max(ans,tans);
        return;
    }
    dfs(pos+1,tleft,tans);
    dfs(pos+1,tleft-tcost[pos],tans+mget[pos]);
}
int main(){
    cin >> t >> n;
    for(int i = 1;i <= n;i++)
        cin >> tcost[i] >> mget[i];
    dfs(1,t,0);
    cout << ans << endl;
    return 0;
}