/*****************
备注：
*****************/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define LL long long
#define MAXM 3010
#define MAXN 3010
const int N =1e5+10;
const int INF =0x3f3f3f3f;
int x,n;
int t[N],m[N];
int f[N];
int main()
{
    cin>>x>>n;
    for(int i=1;i<=n;i++) 
    {
    	cin>>t[i]>>m[i];
	}
    for(int i=1;i<=n;i++)
    {
        for(int j=x;j>=t[i];j--)
        {
            f[j]=max(f[j],f[j-t[i]]+m[i]);
        }
    }
    cout<<f[x];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int f[1010],v[1010],w[1010],t,n;
int main()
{
  cin>>t>>n;
  for(int i=1;i<=n;i++)
    cin>>w[i]>>v[i];
  for(int i=1;i<=n;i++)
    for(int j=t;j>=w[i];j--)
      f[j]=max(f[j],f[j-w[i]]+v[i]);
   cout<<f[t];
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
int q,w,e,r,t,y,u,o,p,s,d,f,g,h,j,l,z,x,c,v,n,m,i,k,a[10001],aa[10000],b[999][99999];
int main()
{
    cin>>m>>n;
    for(i=1;i<=n;i++)
    {
    	cin>>a[i]>>aa[i];
	}
	for(i=0;i<=n;i++)
    {
    	for(j=0;j<=m;j++)
    	{
    		b[i][j]=-99999999;
		}
	}
	b[0][0]=0;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=m;j++)
		{
			b[i][j]=b[i-1][j];
			if(j>=a[i])
			b[i][j]=max(b[i][j],b[i-1][j-a[i]]+aa[i]);
		}
	}
	for(i=0;i<=m;i++)
	{
		x=max(x,b[n][i]);
	}
	cout<<x;
    return 0;
}

野生的01背包了解一下

作为NOIP的第三题，本题确实有点水。其实就是01背包模板。

众所周知，背包问题都有价值 $\texttt{value}$和重量$\texttt{weight}$ 。本题中，将采药的时间$t_{i}$看做是物品重量，$v_{i}$看做是物品价值

有动态转移方程dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

注意 :01背包是倒着搜的。

Code:

#include<bits/stdc++.h>


using namespace std;


int v[1000005],w[1000005],dp[1000005],t,n;


int main()  {


	scanf("%d%d",&t,&n);


	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);


	for(int i=1;i<=n;i++)


		for(int j=t;j>=w[i];j--)


			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);


	printf("%d",dp[t]);


}