竞赛C++竞赛总结2024-04-12周赛总结笔记
Minecraft-Sep4.12周赛总结
总叙
难度$\color{orange}适中$，但是我发挥的不好，主要还是模版没记牢
T1 B3635 硬币问题
题目链接:这里
考点：
动态规划,dp;动态规划初步
难点:
容易与完全背包混淆
比赛时的自己的思路/想法
用完全背包一个个去凑，凑出n
是否AC，若没有，错在哪里了
NO!整道题都理解错了，根本不是背包问题，普通的DP就可以（我是傻子）
正确思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[1000001],a[3]={1,5,11};
int n;
signed main(){
cin>>n;
memset(dp,1145141919810,sizeof(dp));
dp[0]=0;
for(int i=0;i<3;i++){
for(int j=a[i];j<=n;j++){
dp[j]=min(dp[j],dp[j-a[i]]+1);
}
}
cout<<dp[n];
return 0;
}
|
T2 P1510 精卫填海
题目链接:这里
考点：
模拟;动态规划,dp;背包
难点:
几乎没有……
比赛时的自己的思路/想法
用多重背包去取，直到体力值用光
是否AC，若没有，错在哪里了
NO!背包那一块出现了一点问题（好像是模版不太对，还是思路不对）
正确思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
long long a[100005],b[100005],f[100005];
int main(){
int v,n,c;
cin>>v>>n>>c;
f[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++){
for(int j=c-b[i];j>=0;j--){
f[j+b[i]]=max(f[j+b[i]],f[j]+a[i]);
}
}
for(int i=1;i<=c;i++){
if(f[i]>=v){
cout<<c-i;
return 0;
}
}
cout<<"Impossible";
return 0;
}
|
T3 P1833 樱花
题目链接:这里
考点：
动态规划,dp;背包
难点:
计算时间，其他几乎没有……
比赛时的自己的思路/想法
用多重背包去取，直到体力值用光
是否AC，若没有，错在哪里了
NO!最后几分钟写不完了……
正确思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,w[6*N],v[6*N],s[6*N],len,dp[1005];
int main(){
int x1,x2,y1,y2;
scanf("%d:%d %d:%d %d",&x1,&x2,&y1,&y2,&n);
m=(y1-x1)*60+(y2-x2);
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c==0){
w[++len]=a;
v[len]=b;
s[len]=c;
}
for(int j=1;j<=c;j<<=1){
w[++len]=a*j;
v[len]=b*j;
s[len]=j;
c-=j;
}
if(c>0){
w[++len]=a*c;
v[len]=b*c;
s[len]=c;
}
}
for(int i=1;i<=len;i++){
if(s[i]==0){
for(int j=w[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
else{
for(int j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
printf("%d",dp[m]);
return 0;
}
|
T4 P1759 通天之潜水
题目链接:这里
考点：
动态规划,dp
难点:
输出路径
比赛时的自己的思路/想法
先计算总共可以用多久，计算过程中用s[i][j]记录最后输出
是否AC，若没有，错在哪里了
NO!计算路径那里炸了……
正确思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
const int N=10005;
int m,v,n,a[N],b[N],c[N];
int dp[2005][2005],p[2005][2005][105];
void fg(int i,int j,int k){
for(int l=1;l<=p[j-a[i]][k-b[i]][0];l++)
p[j][k][l]=p[j-a[i]][k-b[i]][l];
p[j][k][0]=p[j-a[i]][k-b[i]][0]+1;
p[j][k][p[j][k][0]]=i;
}
int main(){
scanf("%d%d%d",&m,&v,&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
for(int k=v;k>=b[i];k--){
if(dp[j-a[i]][k-b[i]]+c[i]>dp[j][k]){
dp[j][k]=dp[j-a[i]][k-b[i]]+c[i];
fg(i,j,k);
}
else if(dp[j-a[i]][k-b[i]]+c[i]==dp[j][k]){
bool fl=1;
p[j-a[i]][k-b[i]][p[j-a[i]][k-b[i]][0]+1]=i;
for(int l=1;l<=min(p[j-a[i]][k-b[i]][0]+1,p[j][k][0]);l++){
if(p[j-a[i]][k-b[i]][l]<p[j][k][l]){
fg(i,j,k);
break;
}
if(p[j-a[i]][k-b[i]][l]>p[j][k][l]){
fl=0;
break;
}
}
if(p[j-a[i]][k-b[i]][0]+1<p[j][k][0]&&fl){
fg(i,j,k);
}
}
}
}
}
printf("%d\n",dp[m][v]);
for(int i=1;i<=p[m][v][0];i++){
printf("%d ",p[m][v][i]);
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,v,n,a[101],b[101],c[101],f[10001][10001];
string s[201][201];
int main()
{
cin>>m>>v>>n;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--)
for(int k=v;k>=b[i];k--)
{
if(f[j][k]<f[j-a[i]][k-b[i]]+c[i]||(f[j][k]==f[j-a[i]][k-b[i]]+c[i]&&s[j][k]>s[j-a[i]][k-b[i]]+char(i)))
{
f[j][k]=f[j-a[i]][k-b[i]]+c[i];
s[j][k]=s[j-a[i]][k-b[i]]+char(i);
}
}
cout<<f[m][v]<<endl;
for(int i=0;i<s[m][v].size();i++)
cout<<int(s[m][v][i])<<" ";
return 0;
}
|
总结
要好好记录错题，多练习DP有关的题目
