P1048 采药

原$NOIP2005\;pj\;T_3$

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入输出格式

输入格式

第一行有$2$个整数$T$($1≤T≤1000$)和$M$($1≤M≤100$)，用一个空格隔开，$T$代表总共能够用来采药的时间，$M$代表山洞里的草药的数目。接下来的$M$行每行包括两个在$1$到$100$之间（包括$1$和$100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

$1$个整数，表示在规定的时间内可以采到的草药的最大总价值。

INPUT&OUTPUT’s example

Input’s eg #1

Output’s eg #1

说明

对于30%的数据，$M \leq 10$。

对于100%的数据，$M \leq 100$。

分析

典型的$dp$，~~但是还是要讲几句QAQ。~~

设采第$i$种草药需要时间为$t[i]$，所得收益为$v[i]$。

开一个二维数组$f[i][j]$来表示第$i$种草药，花费了最多$j$时间所得的最大收益。

第$i$种草药只有采和不采两种选择：

若不采这种草药，则时间花费$j$没有增多，碰到的草药种数$+1$,收益不变。

即：$f[i][j]=f[i-1][j]$

若采这种草药，则时间花费$j$增加了$t[i]$，碰到的草药种数$+1$,收益增加了$v[i]$。

即：$f[i][j]=f[i-1][j-t[i]]+p[i]$

肯定要让$f[i][j]$尽量的大，所以：

我们的状态转移方程式:

$$f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+p[i])$$

确定了状态转移方程式，就可以开始敲代码了。

代码实现

/* Headers */
#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 1010
using namespace std;
namespace FastIO{
    inline int getint(){
        int res=0,flag=1;
        char word=getchar();
        while(!isdigit(word)){
            if(ch=='-')flag=-1;
            word=getchar();
        }
        while(isdigit(word)){
            s=s*10+word-'0';
            word=getchar();
        }
        return res*flag;
    }
    inline void putint(int target){
        if(target<0){
            target=-target;
            putchar('-');
        }
        if(target>=10)  basic_putint(target/10);
        putchar(target%10+'0');
    }
    inline void new_putint(int x,char external){
        basic_putint(x);
        putchar(external);
    }
}

/* definition */
int t[maxn],v[maxn],f[maxn][maxn];
int T,M,ans;

/* functions */
void init(){
    T=getint();M=getint();
    for(int i=1;i<=M;i++){
       	t[i]=getint();
        v[i]=getint();
	}
}
void init_f(){
    for(int i=0;i<=T;i++)	f[0][i]=0;
}
void work(){
    init();
    init_f();
    for(int i=1;i<=M;i++){
		for(int j=0;j<t[i];j++){
			f[i][j]=f[i-1][j];
		}
		for(int j=t[i];j<=T;j++){
			f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+p[i]);
			ans=max(ans,f[i][j]);
		}
	}
	putint(ans);
}
int main(int argc,char *argv[]){
    #ifndef ltyQwQ's_FILE
	work();
    #endif
	return 0;
}

$Fast\,IO$来自$Handwer\,std$。

洛谷P1048题解