杨老师的照相排列
杨老师的照相排列
解题思路
从题目中我们知道，最多排5排，每排最多30人
要求是第一排从左到右递减，从上到下递减，并且每个人的编号越小，身高越高
假设我们有1,2,33个数字，我们一个一个地排列他们
先排1，显然1只能排在n左上角，即[0,0]的位置，因为如果他排在[0,1]或者[1,0]这些位置那么[0,0]位置放的同学身高应该要比1大，显然这种情况是不可能的。
接着我们排2，他只能排在*的位置,因为如果你放在[0,2],[1,1]的位置就说明[0,1],[1,0]位置的同学身高要比2大，显然这种情况也不可能，因为1的位置定好了，1，2之间没有比2高的了。
⎣⎡1∗0∗00⎦⎤
所以开始动归了
令f[a][b][c][d][e]表示第一排有a个同学，第二排有b个同学，第三排有c个同学，第四排有d个同学，第五排有e个同学的情况下，有多少种排列方式
初始条件当然是f[0][0][0][0][0]=1，每排都没人的时候只有一种排法
递推方程是什么呢？
假设我们现在要排列第i个同学，那么他可能在的位置就是1,2,3,4,5排的最后一个位置，因为其他的位置都被排好了，所以只能放在最后一个。
f[a][b][c][d][e]的初值默认是0
f[a][b][c][d][e]=⎩⎨⎧f[a][b][c][d][e]=f[a][b][c][d][e]+f[a−1][b][c][d][e]ifa>0anda−1>=bf[a][b][c][d][e]=f[a][b][c][d][e]+f[a][b−1][c][d][e]ifb>0andb−1>=cf[a][b][c][d][e]=f[a][b][c][d][e]+f[a][b][c−1][d][e]ifc>0andc−1>=df[a][b][c][d][e]=f[a][b][c][d][e]+f[a][b][c][d−1][e]ifd>0andd−1>=ef[a][b][c][d][e]=f[a][b][c][d][e]+f[a][b][c][d][e−1]ife>0
每种情况都要遍历。
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 31;
ll f[N][N][N][N][N];
int n;
int main(){
while(scanf("%d",&n),n){
int s[5] = {0};
for(int i = 0;i<n;i++)scanf("%d",&s[i]);
memset(f,0,sizeof f);
f[0][0][0][0][0] = 1;
for(int a = 0;a<=s[0];a++)
for(int b = 0;b<=min(a,s[1]);b++)
for(int c = 0;c<=min(b,s[2]);c++)
for(int d = 0;d<=min(c,s[3]);d++)
for(int e = 0;e<=min(d,s[4]);e++){
ll &v = f[a][b][c][d][e];
if(a&&a-1>=b)v+=f[a-1][b][c][d][e];
if(b&&b-1>=c)v+=f[a][b-1][c][d][e];
if(c&&c-1>=d)v+=f[a][b][c-1][d][e];
if(d&&d-1>=e)v+=f[a][b][c][d-1][e];
if(e)v+=f[a][b][c][d][e-1];
}
printf("%lld\n",f[s[0]][s[1]][s[2]][s[3]][s[4]]);
}
return 0;
}
|
最长公共上升子序列
最长公共上升子序列
解题思路
f[i][j]表示a的前i个数字中，以j结尾的最长上升子序列数是多少。
i从1开始遍历到结尾，用temp记录1~j-1中b有多少个数字比a[i]小，如果b[j] = a[j]时，就将f[i-1][j]与temp两个数的最大值记录做f[i][j]的值。
AC代码
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;
const int N = 3010;
int a[N],b[N],f[N][N];
int n;
int main(){
cin>>n;
for(int i =1;i<=n;i++)cin>>a[i];
for(int i =1;i<=n;i++)cin>>b[i];
for(int i = 1;i<=n;i++){
int temp = 1;
for(int j = 1;j<=n;j++){
f[i][j] = f[i-1][j];
if(a[i] == b[j])f[i][j] = max(f[i][j],temp);
if(a[i]>b[j])temp = max(temp,f[i-1][j]+1);
}
}
int res = 0;
for(int i =1;i<=n;i++)res = max(res,f[n][i]);
cout<<res<<endl;
return 0;
}
|
分级
分级
解题思路
序列有一个性质，就是你选择的B[i]一定存在与A[i]中，这样才能保证与a[i]相减时，出现0的结果尽可能地多。
令f[i][j]表示a[1...i-1]对应的b[1...i-1]都已经选择最优且a[i]选择的B[i] = a[j]，f对应的值是最小差值。
a[i]表示原来的数据,a‘[i]表示原来的数据经过排序的结果
对于f[i][j]的求解，就是f[i][j]=min(∑j=1nf[i−1][j])+∣a[i]−a‘[i]∣
翻译成中文就是：前i-1个规模的最优选择+当前选择b[j]与a[i]的差的绝对值
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 2010,INF = 0x3f3f3f3f;
int a[N],b[N],f[N][N];
int n;
int dp(){
for(int i = 1;i<=n;i++){
int temp = INF;
for(int j = 1;j<=n;j++){
temp = min(temp,f[i-1][j]);
f[i][j] = temp+abs(b[j]-a[i]);
}
}
int res = INF;
for(int i = 1;i<=n;i++)res = min(res,f[n][i]);
return res;
}
int main(){
cin>>n;
for(int i =1;i<=n;i++){
cin>>a[i];
b[i] = a[i];
}
sort(b+1,b+n+1);
int res = dp();
reverse(b+1,b+n+1);
res = min(dp(),res);
cout<<res<<endl;
return 0;
}
|
移动服务
移动服务
解题思路
p[i]表示第i个请求的位置，w[i][j]表示从i到j的花费
状态表示：f[i][x][y]完成前i个任务，有一个服务员z的位置是p[i]，其他两个服务员的位置在x,y
状态属性：完成前i个任务的最小花费
求解方式：
策略：采用用当前节点去更新后面节点的方式
对于第i+1个任务，
如果派z位置的服务员去，结果为：f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+w[z][p[i+1]])
如果派x位置的服务员去，结果为：f[i+1][z][y]=min(f[i+1][z][y],f[i][x][y]+w[x][p[i+1]])
如果派y位置的服务员去，结果为：f[i+1][x][z]=min(f[i+1][x][z],f[i][x][y]+w[y][p[i+1]])
AC代码
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
55
56
| #include <bits/stdc++.h>
using namespace std;
const int N = 1010,L = 210;
int w[L][L];
int p[N];
int f[N][L][L];
int n,l;
int main(){
cin>>l>>n;
for(int i =1;i<=l;i++)
for(int j =1;j<=l;j++)
cin>>w[i][j];
for(int i = 1;i<=n;i++)cin>>p[i];
memset(f,0x3f,sizeof f);
p[0] = 1;
f[0][2][3] = 0;
for(int i =0;i<n;i++)
for(int x = 1;x<=l;x++)
for(int y = 1;y<=l;y++){
int z = p[i],now = f[i][x][y];
if(z==x||z==y||y==x)continue;
f[i+1][x][y] = min(f[i+1][x][y],now+w[z][p[i+1]]);
f[i+1][z][y] = min(f[i+1][z][y],now+w[x][p[i+1]]);
f[i+1][x][z] = min(f[i+1][x][z],now+w[y][p[i+1]]);
}
int res = 1e9;
for(int x = 1;x<=l;x++)
for(int y = 1;y<=l;y++){
int z = p[n];
if(z==x || z==y||y==x)continue;
res = min(res,f[n][x][y]);
}
cout<<res<<endl;
return 0;
}
|
传值条
传值条
解题思路
状态表示：
集合：f[k][x1][x2]表示当前两条线走了k步，第一条线从(1,1)->(x1,k-x1),第二条线从(1,1)->(x2,k-x2)的所有组合方式
属性：两条线的最大权值
状态计算：
t是当前点的权值，因为两条线的点不能重合所有就要看这两个点究竟会不会重合，不重合就计算两次，重合只计算一次
计算的方式包括四种情况
- 第一条线：向右 第二条线：向右
f[k-1][x1-1][x2-1]+t
- 第一条线：向右 第二条线：向下
f[k-1][x1-1][x2]+t
- 第一条线：向下 第二条线：向右
f[k-1][x1][x2-1]+t
- 第一条线：向下 第二条线：向下
f[k-1][x1][x2]+t
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 55;
int w[N][N];
int f[2*N][N][N];
int m,n;
int main(){
cin>>n>>m;
for(int i =1;i<=n;i++)
for(int j = 1;j<=m;j++)
cin>>w[i][j];
for(int k = 2;k<=n+m;k++)
for(int x1 = max(1,k-m);x1<=min(k-1,n);x1++)
for(int x2 = max(1,k-m);x2<=min(k-1,n);x2++){
int t = w[x1][k-x1];
if(x2 != x1) t += w[x2][k-x2];
for(int a = 0;a<2;a++)
for(int b =0;b<2;b++)
f[k][x1][x2] = max(f[k][x1][x2],f[k-1][x1-a][x2-b]+t);
}
cout<<f[n+m][n][n]<<endl;
return 0;
}
|
微信
支付宝
