杭电pj备战专题-1

DP专场,还比较简单

T1 数塔

dp[i][j] 第i层第j列到底部的最优解

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])

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
#include<bits/stdc++.h>
using namespace std;
int T,n;
int dp[105][105];
int main()
{
cin>>T;
while(T--)
{
memset(dp,0,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>dp[i][j];
}
}
for(int i=n;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
}
}
cout<<dp[1][1]<<endl;
}
}

T2 01背包

w[i] 第i个物品的价值

v[i] 第j个物品的体积

空间优化

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

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;
int w[1005],v[1005];
int dp[1005];
int m,n;
int main()
{
while(cin>>m>>n&&m!=-1&&n!=1)
{
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[m]<<endl;
}
}

T3 有限制的01背包

初始化改一改,dp[0]=0,剩下初始化成-inf

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
#include<bits/stdc++.h>
using namespace std;
int w[1005],v[1005];
int dp[1005];
int m,n;
int main()
{
while(cin>>m>>n&&m!=-1&&n!=1)
{
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(int i=1;i<=m;i++)
{
dp[i]=-100000;
}
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
if(dp[m]<0)
cout<<-1<<endl;
else
cout<<dp[m]<<endl;
}
}

T4 完全+二维背包

完全 01倒过来 二维 加一维

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;
int n,m,k,s;
int w[1005],v[1005];
int dp[1005][1005];
int main()
{
while(cin>>n>>m>>k>>s)
{
memset(dp,0,sizeof(dp));
memset(w,0,sizeof(w));
memset(v,0,sizeof(v));
for(int i=1;i<=k;i++)
{
cin>>w[i]>>v[i];
}
for(int i=1;i<=k;i++)
{
for(int j=v[i];j<=m;j++)
{
for(int p=1;p<=s;p++)
{
dp[j][p]=max(dp[j][p],dp[j-v[i]][p-1]+w[i]);
}
}
}
if(dp[m][s]<n)
{
cout<<-1<<endl;
}
else
{
for(int i=0;i<=m;i++)
{
if(dp[i][s]>=n)
{
cout<<m-i<<endl;
break;
}
}
}
}
}

T5 丑数

dp[i]=min(dp[i1]x2,dp[i2]x3,dp[i3]x5,dp[i4] 7) i1,i2,i3,i4<i&&dp[i1…i4]>dp[i-1]

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
49
50
51
52
53
54
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll dp[6000],a,b,c,d;
int main()
{
dp[1]=1;
dp[2]=2;
dp[3]=3;
dp[4]=4;
dp[5]=5;
dp[6]=6;
for(int i=7;i<=5900;i++)
{
for(int j=1;j<=i;j++)
{
if(dp[j]*2>dp[i-1])
{
a=dp[j]*2;
break;
}
}
for(int j=1;j<=i;j++)
{
if(dp[j]*3>dp[i-1])
{
b=dp[j]*3;
break;
}
}
for(int j=1;j<=i;j++)
{
if(dp[j]*5>dp[i-1])
{
c=dp[j]*5;
break;
}
}
for(int j=1;j<=i;j++)
{
if(dp[j]*7>dp[i-1])
{
d=dp[j]*7;
break;
}
}
dp[i]=min(a,min(b,min(c,d)));
}
while(cin>>n&&n!=0)
{
cout<<dp[n]<<endl;
}
}

T6 机器分配

dp[i][j] 前i个公司分前j个机器

dp[i][j]=max(dp[i][j],dp[i-1][j-k]+f[i][k]) k是分给第j个公司的机器数

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
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
int f[105][105];
int n,m;
int main()
{
while(cin>>n>>m)
{
memset(dp,0,sizeof(dp));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>f[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=0;k<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k]+f[i][k]);
}
}
}
cout<<dp[n][m]<<endl;
}
}

T7 搬寝室

这里的多组数据好坑啊。。。罚了我60分钟

先排序一波

dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j])

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
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[2005];
int dp[2005][2005];
int main()
{
while(cin>>n>>k)
{
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=0;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
dp[i][j]=100000000;
}
}
dp[0][0]=0;
for(int i=2;i<=n;i++)
{
for(int j=1;j*2<=i;j++)
{
dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]);
}
}
cout<<dp[n][k]<<endl;
}

}

T8 龟兔赛跑

注意用double来比较

dp[i]表示起点到第i个充电桩的最优解

充电必须充满才值,把起点和终点都看作特殊的充电桩

dp[i]=min(dp[i],dp[j]+T(p[j],p[i])+t)

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
#include<bits/stdc++.h>
using namespace std;
double c,t,vr,vt1,vt2,p[105],dp[105];
int n,l;
double T(double a,double b)
{
if(c>=b-a)return 1.0*(b-a)/vt1;
else return 1.0*c/vt1+1.0*(b-a-c)/vt2;
}
int main()
{
while(cin>>l>>n>>c>>t>>vr>>vt1>>vt2)
{
for(int i=1;i<=n;i++)
{
cin>>p[i];
}
dp[0]=0;
p[0]=0;
p[n+1]=l;
for(int i=1;i<=n+1;i++)
{
dp[i]=T(0,p[i]);
for(int j=1;j<i;j++)
{
dp[i]=min(dp[i],dp[j]+T(p[j],p[i])+t);
}
}
if(dp[n+1]>1.0*l/vr)
{
cout<<"Good job,rabbit!\n";
}
else
{
cout<<"What a pity rabbit!\n";
}
}
}