1.A
没什么难度，直接算就可以了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Yes printf("Yes\n")
#define No printf("No\n")
#define YES printf("YES\n")
#define NO printf("NO\n")
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int dp[100005];
int n;
int a[100005];
signed main(){
n=read();
rep(i,n)a[i]=read();
memset(dp,INF,sizeof(dp));
dp[1]=0;
for(int i=2;i<=n;i++){
for(int j=i-1;j>=i-2;j--)dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
}
printf("%lld",dp[n]);
return 0;
}
2.B
和上一题差不多，只不过要从 \(k\) 步之前转移来。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Yes printf("Yes\n")
#define No printf("No\n")
#define YES printf("YES\n")
#define NO printf("NO\n")
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int dp[100005];
int n,k;
int a[100005];
signed main(){
n=read(),k=read();
rep(i,n)a[i]=read();
memset(dp,INF,sizeof(dp));
dp[1]=0;
for(int i=2;i<=n;i++){
for(int j=i-1;j>=max(i-k,1LL*1);j--)dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
}
printf("%lld",dp[n]);
return 0;
}
3.C
令 \(dp_{i,j}\) 表示第 \(i\) 天选第 \(j\) 个活动的最大快乐值，转移即可。
话说为什么写作业有快乐值
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Yes printf("Yes\n")
#define No printf("No\n")
#define YES printf("YES\n")
#define NO printf("NO\n")
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int dp[100005][5];
int n;
int a[100005],b[100005],c[100005];
signed main(){
n=read();
rep(i,n)a[i]=read(),b[i]=read(),c[i]=read();
rep(i,n){
dp[i][1]=max(dp[i-1][2],dp[i-1][3])+a[i];
dp[i][2]=max(dp[i-1][1],dp[i-1][3])+b[i];
dp[i][3]=max(dp[i-1][1],dp[i-1][2])+c[i];
}
printf("%lld",max(dp[n][1],max(dp[n][2],dp[n][3])));
return 0;
}
4.D
背包板子题
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define INF 0x3f3f3f
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
int n,w;
struct Item{
int w,v;
}a[105];
int dp[100005];
signed main(){
n=read(),w=read();
rep(i,n){
a[i].w=read(),a[i].v=read();
}
for(int i=1;i<=n;i++){
for(int j=w;j>=a[i].w;j--){
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
printf("%lld",dp[w]);
return 0;
}
5.E
发现这道题答案不超过 \(10^5\)，那么就可以设 \(dp_i\) 表示价值为 \(i\) 时的最小重量，最后计算即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int n,W;
int dp[100005];
signed main(){
n=read(),W=read();
memset(dp,INF,sizeof(dp));
dp[0]=0;
rep(i,n){
int w=read(),v=read();
FOR(j,100000,v){
dp[j]=min(dp[j],dp[j-v]+w);
}
}
FOR(i,100000,0){
if(dp[i]<=W){
out(i);
return 0;
}
}
return 0;
}