这题比较水。。 普通的一道 dp 题，只不过 dp 数组用 string 类型而已 定义 dpl,r,f 为当前以使用的区间为 [l,r] 且当前的数与 lowerBound 在 [l,r] 上的数值的关系为 f 时最小的数 当x>lowerBound时 f=2 当 x<lowerBound 时 f=0 否则 f=1 而后很容易的就能 dp 了 代码如下：
#include<bits/stdc++.h> using namespace std; #define M 55 string dig,low; string dp[M][M][3]; int getflag(string A,string B){ if(A<B)return 0; if(A==B)return 1; return 2; } void Min(string &A,string B){ if(B=="")return; if(A==""||A>B)A=B; } int main(){ cin>>dig>>low; int n=dig.size(); for(int i=0;i<n;i++){ int flag=getflag(dig.substr(0,1),low.substr(i,1)); dp[i][i][flag]=dig.substr(0,1); } for(int i=n-1;~i;i--) for(int j=i+1;j<n;j++) for(int f=0;f<3;f++){ if(dp[i+1][j][f]!=""){ string now=dig[j-i]+dp[i+1][j][f]; int flag=getflag(now,low.substr(i,j-i+1)); Min(dp[i][j][flag],now); } if(dp[i][j-1][f]!=""){ string now=dp[i][j-1][f]+dig[j-i]; int flag=getflag(now,low.substr(i,j-i+1)); Min(dp[i][j][flag],now); } } Min(dp[0][n-1][1],dp[0][n-1][2]); if(dp[0][n-1][1]!="")cout<<dp[0][n-1][1]<<endl; else puts("-1"); return 0; }