动态规划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;
}