动态规划2

P1616 疯狂的采药

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,M=1e7+5;
int n,m,w[N],v[N],f[M];
signed main(){
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&w[i],&v[i]);
	for(int i=1;i<=n;i++)
		for(int j=w[i];j<=m;j++)
			f[j]=max(f[j],f[j-w[i]]+v[i]);
	printf("%lld",f[m]);
	return 0;
}

P1833 樱花

• 背包问题 -- 二进制拆分
• 代码优化：快读

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,a1,a2,b1,b2,m,nn,ti,ci,pi,l,r;
int f[1010];
deque< pair<int,int> >q;
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
signed main()
{
	a1=read();b1=read();a2=read();b2=read();n=read();
	m=(a2-a1)*60+b2-b1;
	for(register int i=1;i<=n;i++)
	{
		ti=read();ci=read();pi=read();
		if(pi==0) for(register int j=ti;j<=m;j++) f[j]=max(f[j],f[j-ti]+ci);
		else
		for(register int j=0;j<ti;j++)
		{
			while(q.size()) q.pop_front();
			l=1;r=0;
			int maxp=(m-j)/ti;
			for(register int p=0;p<=maxp;p++)
			{
				while(q.size()&&f[j+ti*p]-ci*p>=q.back().second) q.pop_back();
				q.push_back(make_pair(p,f[j+ti*p]-ci*p));
				while(q.size()&&q.front().first<p-pi) q.pop_front();
				f[j+ti*p]=max(f[j+ti*p],q.front().second+ci*p);
			}
		}
	}
	printf("%d",f[m]);
}

P1077 摆花

#include <bits/stdc++.h>
using namespace std;
int f[105][105];
int a[105];
int n,m;
int main(){
    cin>>n>>m;
	 for(int i=1;i<=n;i++) cin>>a[i];
	 f[0][0]=1;
	 for(int i=1;i<=n;i++){
	 	for(int j=0;j<=m;j++){
	 		for(int k=0;k<=min(j,a[i]);k++){
	 			f[i][j]=(f[i][j]+f[i-1][j-k])%1000007;
			 }
		 }
	 }
	 cout<<f[n][m];
	 return 0;
}

P1064 金明的预算方案

#include <bits/stdc++.h> 
using namespace std;  
int m,n;
int mw[32005],mv[65],fw[65][3],fv[65][3],f[32005],v,p,q;    
int main()  
{  
    cin>>n>>m;  
    for(int i=1;i<=m;i++){  
    cin>>v>>p>>q;  
    if(!q){   
        mw[i]=v; 
        mv[i]=v*p; 
    }  
    else{
        fw[q][0]++;
        fw[q][fw[q][0]]=v;
        fv[q][fw[q][0]]=v*p;
    }  
    }  
    for(int i=1;i<=m;i++)  
    for(int j=n;j>=mw[i];j--){ 
        f[j]=max(f[j],f[j-mw[i]]+mv[i]);   
        if(j>=mw[i]+fw[i][1])f[j]=max(f[j],f[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]);  
        if(j>=mw[i]+fw[i][2])f[j]=max(f[j],f[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]);  
        if(j>=mw[i]+fw[i][1]+fw[i][2])  
        f[j]=max(f[j],f[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]);  
    }   
    cout<<f[n]<<endl;  
    return 0;  
}