[√] Mr Youngs Picture Permutations
[√] LCIS
[√] Making the Grade
[√] Mobile Service
[] 传纸条
[] I-country
sol:
考虑限制要求：每一排从左往右必须身高递减，每一列从第一排到最后一排身高也必须递减。
则可以发现填数时必须保证：如果从大往小填数，现在填第i行，则第i-1行填了的数必须多于第i行填了的数。
所以可以直接利用这样一种关系进行转移即可。
code：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int k,a[6],n[6],f[31][16][11][9][7];
int main()
{
while(cin>>k) {
if(k==0)break;
memset(n,0,sizeof(n));
memset(f,0,sizeof(f));
for(int i=1;i<=k;i++) scanf("%d",&n[i]);
f[0][0][0][0][0]=1;
for(a[1]=0;a[1]<=n[1];a[1]++)
for(a[2]=0;a[2]<=n[2];a[2]++)
for(a[3]=0;a[3]<=n[3];a[3]++)
for(a[4]=0;a[4]<=n[4];a[4]++)
for(a[5]=0;a[5]<=n[5];a[5]++) {
int t=f[a[1]][a[2]][a[3]][a[4]][a[5]];
if(a[1]<n[1]) f[a[1]+1][a[2]][a[3]][a[4]][a[5]]+=t;
if(a[2]<n[2]&&a[1]>a[2]) f[a[1]][a[2]+1][a[3]][a[4]][a[5]]+=t;
if(a[3]<n[3]&&a[2]>a[3]) f[a[1]][a[2]][a[3]+1][a[4]][a[5]]+=t;
if(a[4]<n[4]&&a[3]>a[4]) f[a[1]][a[2]][a[3]][a[4]+1][a[5]]+=t;
if(a[5]<n[5]&&a[4]>a[5]) f[a[1]][a[2]][a[3]][a[4]][a[5]+1]+=t;
}
cout<<f[n[1]][n[2]][n[3]][n[4]][n[5]]<<endl;
}
return 0;
}sol:
结合LIS和LCS的经典解法，可以设计\(f[i][j]\)表示：
? A数列的前i个，B数列的前j个中，可以构成的以b[j]为结尾的LCIS长度。
考虑转移：
\[
f[i][j]=f[i-1][j]\ (A[i]!=B[j])\f[i][j]=max_{0<=k<j,B[k]<B[j]}\lbrace{f[i-1][k]}\rbrace+1\ (A[i]==B[j])\\]
可以发现直接转移为\(n^3\)。
实际上可以发现，可以用一个变量Max来维护\(f[i-1][]\)的最大值。
每次更新完\(f[i][j]\)，只需新加入一个\(f[i-1][j]\)即可。
而为了保证Max所代表的LCIS能够在后面被接上，则更新Max前需判断是否\(A[i]>B[j]\)。
code：
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;
IL int gi() {
RG int x=0,w=0; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return w?-x:x;
}
const int N=510;
int n,m,Max,ans,a[N],b[N],f[N][N],p[N][N];
IL void print(int x,int y) {
while(a[x]!=b[y]) --x;
if(p[x][y]) print(x-1,p[x][y]);
printf("%d ",a[x]);
}
int main()
{
RG int i,j,y,T=1;
while(T--) {
for(i=1,n=gi();i<=n;++i) a[i]=gi();
for(i=1,m=gi();i<=m;++i) b[i]=gi();
memset(f,0,sizeof(f));
memset(p,0,sizeof(p));
for(i=1;i<=n;++i) {
for(j=1,y=Max=0;j<=m;++j) {
f[i][j]=f[i-1][j];
if(a[i]>b[j]&&f[i-1][j]>Max) Max=f[i][j],y=j;
// 此处用a[i]>b[j]，是为了保证后面如果存在a[i]==b[j]时，b[j]>a[i]，很巧妙
if(a[i]==b[j]) f[i][j]=Max+1,p[i][j]=y;
}
}
for(j=1,ans=0;j<=m;++j)
if(f[n][j]>ans) ans=f[n][j],y=j;
printf("%d\n",ans);
if(ans) print(n,y);
putchar('\n');
}
return 0;
}
// 最长公共上升子序列
sol:
只需考虑不下降的构造即可，不上升的构造同理。
设\(f[i][x]\)表示填了前i个数，第i个数填的是x时的最小答案。
那么容易得到转移方程为：
\[
f[i][x]=min_{0<=k<=x}\lbrace{f[i-1][k]}\rbrace+\arrowvert A[i]-x\arrowvert
\]
但是注意到值域有\(10^9\)，所以还不能直接做。
这时需要意识到一个结论：改造出来的数列的元素全是原来数列里有的数。
证明：数学归纳法。
对于n=1，显然成立。
对于n=k?1时，假设其满足由原数列的数构成最优解。那么，考虑对于n=k。
当\(A_n≥B_{n?1}\)时（B为之后的数列）显然直接用\(A_n\)最优。
当\(A_n ＜ B_{n-1}\)时有两种选择:
① 填\(B_{n-1}\)。
② 把\(B_j…B_n\)全部向下调整为t。此时对于\(A_j…A_n\)的中位数mid，
如果存在\(mid ≥ B_{j-1}\),则\(t=mid\)时最优，否则\(t=B_{j-1}\)时最优。
综上，无论哪种最优情况下都为A[]中出现过的数，命题成立。
基于此，则可以直接把能填的数个数范围缩小到2000，加上与上一题类似的用变量min维护f最小值，在直接转移，做到\(n^2\)
code:
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;
IL int gi() {
RG int x=0,w=0; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return w?-x:x;
}
const int N=2e3+7;
const int inf=0x3f3f3f3f;
LL ans1,ans2,f[N][N];
int n,a[N],b[N];
IL bool cmp(int a,int b) {return a>b;}
IL void DP() {
RG int i,j;
RG LL Min;
memset(f,0,sizeof(f));
for(i=1;i<=n;++i) {
for(j=1,Min=inf;j<=n;++j) {
Min=min(Min,f[i-1][j]);
f[i][j]=Min+abs(a[i]-b[j]);
}
}
}
int main()
{
RG int i;
for(i=1,n=gi();i<=n;++i) a[i]=b[i]=gi();
sort(b+1,b+n+1);
ans1=ans2=inf;
for(i=1,DP();i<=n;++i) ans1=min(ans1,f[n][i]);
sort(b+1,b+n+1,cmp);
for(i=1,DP();i<=n;++i) ans2=min(ans2,f[n][i]);
printf("%lld\n",min(ans1,ans2));
return 0;
}sol:
先考虑最直接的状态：\(f[i][x[y][z]\)表示解决了前面i个请求，三个服务员分别位于x,y,z时的最小花费。
那么容易写得转移：
\[
f[i+1][p_{i+1}][y][z]=min(f[i+1][p_{i+1}][y][z],f[i][x][y][z]+cost(x,p_{i+1}))\f[i+1][x][p_{i+1}][z]=min(f[i+1][x][p_{i+1}][z],f[i][x][y][z]+cost(y,p_{i+1}))\f[i+1][x][y][p_{i+1}]=min(f[i+1][x][y][p_{i+1}],f[i][x][y][z]+cost(z,p_{i+1}))\\]
时空复杂度为：O(\(1000*200^3\)),显然不行。
但是发现实际上并不需要记录三个人的位置，只需记录两个人的即可，第三者必然在\(p_i\)位置上。
所以，\(f[i][x[y]\)表示解决了前面i个请求，两个服务员分别位于x,y，另一个位于\(p_i\)时的最小花费。
转移为：
\[
f[i+1][p_i][y]=min(f[i+1][p_i][y],f[i][x][y]+cost(x,p_{i+1}))\f[i+1][x][p_i]=min(f[i+1][x][p_i],f[i][x][y]+cost(y,p_{i+1}))\f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+cost(p_i,p_{i+1}))\\]
code:
#include <bits/stdc++.h>
using namespace std;
inline int gi() {
int x=0, w=0; char ch=0;
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return w?-x:x;
}
const int Pos=210;
const int N=1010;
int T,L,n,ans,f[N][Pos][Pos],c[Pos][Pos],pos[N];
int main ()
{
T=gi();
while(T--) {
ans=0x3f3f3f3f;
memset(c,0,sizeof(c));
memset(pos,0,sizeof(pos));
memset(f,0x3f3f3f3f,sizeof(f));
L=gi(),n=gi();
for(int i=1;i<=L;++i)
for(int j=1;j<=L;++j) c[i][j]=gi();
for(int i=1;i<=n;++i) pos[i]=gi();
pos[0]=3,f[0][1][2]=0;
for(int k=0;k<n;++k)
for(int i=1;i<=L;++i)
if(i!=pos[k])
for(int j=1;j<=L;++j) {
if (j!=pos[k]&&j!=i) {
if(i!=pos[k+1]&&j!=pos[k+1])
f[k+1][i][j]=min(f[k+1][i][j],f[k][i][j]+c[pos[k]][pos[k+1]]);
if(j!=pos[k+1])
f[k+1][pos[k]][j]=min(f[k+1][pos[k]][j],f[k][i][j]+c[i][pos[k+1]]);
if(i!=pos[k+1])
f[k+1][i][pos[k]]=min(f[k+1][i][pos[k]],f[k][i][j]+c[j][pos[k+1]]);
}
}
for(int i=1;i<=L;++i)
for(int j=1;j<=L;++j)
if(i!=pos[n]&&j!=pos[n]&&i!=j) ans=min(ans,f[n][i][j]);
printf("%d\n",ans);
}
return 0;
}
原文：https://www.cnblogs.com/Bhllx/p/10927920.html