P1025 小飞侠的游园方案解题报告

Published on 2009 / 04 / 26

类似 0/1背包的问题，还是记忆化加动态规划，很简单就可以过。

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
Accepted 有效得分：100 有效耗时：0ms

附代码（C语言）：

#include<stdio.h>
#include<stdlib.h>
int N,t,maxfi,fi[101],ti[101],save[101][1002];
int MaxHappy(int site,int time);
int Max(int a,int b);
int main()
{
    scanf("%d",&N);
    scanf("%d",&t);
    int i;
    for(i=0;i<N;i++)
        scanf("%d %d",&fi,&ti);
    maxfi=MaxHappy(0,t);
    printf("%d",maxfi);
    return 0;
}
int MaxHappy(int site,int time)
{
    if(save[site][time]==0)
        if(site<N&&time>0)
        {
            if(time>=ti[site])
                save[site][time]=Max(MaxHappy(site+1,time),
                fi[site]+MaxHappy(site+1,time-ti[site]));
            else
                save[site][time]=MaxHappy(site+1,time);
        }
    return save[site][time];
}
int Max(int a,int b)
{
    if(a<b)
        a=b;
    return a;
}