A题
暴力打表后，找出答案开头的数字是一段连续的规律数字，后面跟上一串\(8\)，顺利用此写法通过
B题
一眼爆搜，但没有调过，就按照题目所说的搜索就行了，注意一些小的剪枝和常熟问题即可。
此处郑重提示：\(string\)类型赋值为另一个\(string\)会有\(O(n)\)的常数，小心被卡常。
如果遇到要打印方案的问题，存字符串答案时用全局变量$string \(存，添加用\)+=\(，删除用 pop_back()，保证常数为\)O(1)\(** . **另外到了终点不管是否走过所有平台都需要**\)return\(,如果已有答案，直接\)return$,将不等于 # 的全部设成\(1\)，即可。同时注意对走过的点打标记**，走过的就不判了，在某个方向上遇到一个\(1\)，就\(break\)掉。
至于时间复杂度，粗略算下来，不会超过\(O(T*2^{14}*3^{12})\) , 即为\(5*6\)方格下的最高时间复杂度，但远比它小得多,所以能够通过本题 \(2s\) 的时限。
int n,m,xa,ya,xb,yb,t,tag,mark[N][N];
int a[N][N];
string ans;//剪枝3
bool flag;
//注意 TLE原因：string tmp=a有常数为 n*m 的影响，而加上一个数是O(1),pop_back也是O(1)的。
inline void dfs(register int x,register int y,register int lst,register int cnt){
if(flag) return;//剪枝1
if(x==xb&&y==yb){
if(cnt==tag){
cout<<"YES"<<'\n';
cout<<ans<<'\n';//剪枝4
flag=true;
}
return;//剪枝2
}
register int nx,ny;
if(lst!=2){
nx=x-1;
ny=y;
while(nx>0){
if(a[nx][ny]==1&&!mark[nx][ny]){//mark数组标记是否遍历过
mark[nx][ny]=1;
ans+='U';
dfs(nx,ny,1,cnt+1);
ans.pop_back();
mark[nx][ny]=0;//剪枝5
break;//剪枝6
}
nx--;
}
}
if(flag) return;
if(lst!=1){
nx=x+1;
ny=y;
while(nx<=n){
if(a[nx][ny]==1&&!mark[nx][ny]){
mark[nx][ny]=1;
ans+='D';
dfs(nx,ny,2,cnt+1);
ans.pop_back();//O(1)
mark[nx][ny]=0;
break;
}
nx++;
}
}
if(flag) return;
if(lst!=4){
nx=x;
ny=y-1;
while(ny>0){
if(a[nx][ny]==1&&!mark[nx][ny]){
mark[nx][ny]=1;
ans+='L';
dfs(nx,ny,3,cnt+1);
ans.pop_back();
mark[nx][ny]=0;
break;
}
ny--;
}
}
if(flag) return;
if(lst!=3){
nx=x;
ny=y+1;
while(ny<=m){
if(a[nx][ny]==1&&!mark[nx][ny]){
mark[nx][ny]=1;
ans+='R';
dfs(nx,ny,4,cnt+1);
ans.pop_back();
mark[nx][ny]=0;
break;
}
ny++;
}
}
if(flag) return;
}
signed main(){
cin>>t;
while(t--){
tag=0;
flag=false;
cin>>n>>m;
for(register int i=1;i<=n;i=-~i){
for(register int j=1;j<=m;j=-~j){
char op;
cin>>op;
mark[i][j]=0;
if(op=='#'){
a[i][j]=0;
continue;
}
a[i][j]=1;
tag++;
if(op=='S'){
xa=i;
ya=j;
}
if(op=='T'){
xb=i;
yb=j;
}
}
}
ans="";
mark[xa][ya]=1;
a[xa][ya]=0;
dfs(xa,ya,-1,1);//开始的 S 节点算一个
if(!flag){
cout<<"NO"<<'\n';
}
}
return 0;
}
心得
以后给这种题多一点时间，多练一些类似的题，多学一些剪枝小技巧，多学一些好的码风即可。
C题
没想到吧，也是爆搜。首先如果不考虑权值的问题，怎么做？
不考虑权值
考虑两种情况
1.本身已经定下来了，就直接加上贡献往下一个位置算即可。
2.是\(？\)，此时求的是字典序从大到小的第\(k\)个，考虑将$ N,O,I,P$ 四个字母，按照字典序降序排列，再一个一个尝试，直到总的情况数\(>=k\)即可直接输出，然后直接\(return\)掉。
时间复杂度:每次搜索均为有效搜索，扫了\(n\)个位置，为\(O(n+k)\)
考虑权值
其实仍然是那两种情况和方法，只不过此时就不能在最后判断权值之和是否\(>=x\)了，这样会导致很多无用的搜索次数。考虑一个可行性剪枝，如果当前的权值之和\(+\)后面所能有的最大权值之和都比\(x\)小，那么此时这个状态就是无用的，可以直接不用继续搜索了。这样可以保证每一次搜索均有效，时间复杂度为\(O(n+k)\),但空间复杂度，就要看栈空间的大小了，所以\(n\)应该取不到 \(2e5\)
至于如何实现求出\(i\)到\(n\)的所有可能情况中权值最大是多少，可以用\(DP\)来求解。
设\(f[i][j]\)表示第\(i\)个点的字母为\(j\)号的最大权值之和，如果\(i\)本来就有，直接枚举\(i+1\)是哪个字符，进行转移即可；反之，便枚举\(i\)和\(i+1\)的字符进行转移即可。
但要注意，\(x>=0\)，当\(x=0\)时，\(DP\)数组如果没有初始化为负无穷，会导致全部状态都可以，将退化成\(O(4^n)\)，甚至答案也会错。初始化\(DP\)数组的最后一个位置也就是\(n\)的值，有只需要赋值 \(0\) 给有的字符的那一维，否则\(4\)种情况都要初始化为 \(0\) 。
string a;
int n,x,k;
int w[10][10];
int f[N][6],cnt;
char dc[5]={'P','O','N','I'};//字典序的限制
map<char,int> m;
bool flag=false;
void dfs(int cur,int sum){
if(flag) return;//剪枝1
if(cur==n+1){
if(sum>=x){
++cnt;
if(cnt==k){//剪枝2
for(int i=1;i<=n;i++){
cout<<a[i];
}
flag=true;
}
}
return;//剪枝3
}
if(a[cur]!='?'){
int res=w[m[a[cur-1]]][m[a[cur]]];
dfs(cur+1,sum+res);
}else{
for(int i=0;i<4;i++){
a[cur]=dc[i];
int res=w[m[a[cur-1]]][m[a[cur]]];
if(sum+f[cur][m[dc[i]]]+res>=x){//剪枝4
dfs(cur+1,sum+res);
}
a[cur]='?';
}
}
}
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
m['N']=1;
m['O']=2;
m['I']=3;
m['P']=4;
cin>>n>>x>>k;
cin>>a;
a=' '+a;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin>>w[i][j];
}
}
memset(f,-0x3f3f3f3f,sizeof(f));
if(a[n]=='?') f[n][0]=f[n][1]=f[n][2]=f[n][3]=f[n][4]=0;
else f[n][m[a[n]]]=0;
//注意初始化为负无穷大的问题+最后一个位置是否有数的问题
for(int i=n-1;i>0;i--){
if(a[i]!='?'){
for(int j=1;j<=4;j++){
f[i][m[a[i]]]=max(f[i][m[a[i]]],f[i+1][j]+w[m[a[i]]][j]);
}
}else{
for(int j=1;j<=4;j++){
for(int k=1;k<=4;k++){
f[i][j]=max(f[i][j],f[i+1][k]+w[j][k]);
}
}
}
}
dfs(1,0);
if(!flag){
cout<<"-1";
}
return 0;
}
心得
DP不一定是某个题的全部或正解，有时也是辅助加速搜索或帮助减少不必要的枚举次数的手段。
D题
此题一眼区间\(DP\)，我本来以为要将操作次数放入状态中，结果会发现这个式子可以变形为：
\(a*k+b*\sum_{i=1}^{k}(max-min)^2\)
-> \(\sum_{i=1}^{k}a+\sum_{i=1}^{k}b*(max-min)^2\)
-> \(\sum_{i=1}^{k}a+b*(max-min)^2\)
会发现此时的这个式子，不需要记录操作次数，只需要知道一个区间的最大最小值，将代价累加，就可以自动省去k的维度。
所以，我们设\(f[i][j][ma][mi]\)表示区间\([i,j]\)删了一部分后还剩有的数中最大值为\(ma\),最小值为\(mi\),的最小代价。\(g[i][j]\)表示删除区间\([i,j]\)后不剩余任何数字的最小代价（会分为整体删除和部分删完后合在一起再删除）。
显然，原数组需要将大小离散化，但顺序不能变。离散化后：
初始化：
先全部设为正无穷大，再枚举区间赋上初始值。
\(g[i][j]=a+b*(ma-mi)^2\)
\(f[i][j][ma][mi]=0\),没有删任何数，代价为\(0\)，其中\(ma,mi\)表示区间\([i,j]\)中的最大值与最小值，\(O(n^3)\)枚举即可。
转移：
第一种情况，枚举断点\(k\)，一定可以使得原区间\(ma,mi\)在同侧，在异侧一定不会最优，因为会再多用一次的代价。那么就可以将\(k\)左边的部分删除一部分后再和右边的一起消除，也可以将\(k\)右边的部分删除一部分后再和左边的一起消除。
即为：
\(f[i][j][ma][mi]=\min_{k=i}^{j-1}{f[i][k][ma][mi]+g[k+1][j]}\)
\(f[i][j][ma][mi]=\min_{k=i}^{j-1}{f[k+1][j][ma][mi]+g[i][k]}\)
此时，转移时显然多转移了一些情况，但它不会比最优解更优，我们只需要保证能递推出最优解即可。
第二种情况，是关于\(g\)数组的递推，\(g\)数组应该是边算\(f\)数组边更新的。
\(g[i][j]=\min(f[i][j][ma][mi]+a+b*(ma-mi)^2)\)
这个应该十分的显然，剩下了了一部分,直接一次性整体删掉即可。
第三种情况，我们可以将下标为\(j+1\)的元素和区间\([i.j]\)一起消除之后合并之后再消除，即为:
\(f[i][j+1][max(ma,a[j+1])][min(mi,a[j+1])]=min(f[i][j][ma][mi])\)
此处应该当\(f[i][j][ma][mi]\)算完以后再递推，因为需要用到它的值。
因为此刻只是放进去了而已，所以应该是\(0\)代价的，如果用\(f[i][j-1]\)来递推，就不知道区间\([i,j-1]\)的最大最小值是多少了（填表法），但去更新区间\([i,j+1]\)，就可以知道此区间的最大最小值了，直接取\(max,min\)即可（刷表法），最后注意初始化即可。
答案就是\(g[1][n]\)，删除整个区间后不剩余任何数字的最小代价。
int n,a,b,w[N],c[N],ys[N];
int g[N][N],f[N][N][N][N],len;
signed main(){
scanf("%lld",&n);
scanf("%lld %lld",&a,&b);
for(int i=1;i<=n;i++){
scanf("%lld",&w[i]);
c[i]=w[i];
}
memset(f,0x3f3f3f3f,sizeof(f));
memset(g,0x3f3f3f3f,sizeof(g));
sort(c+1,c+1+n);
len=unique(c+1,c+1+n)-c-1;
for(int i=1;i<=n;i++){
int t=lower_bound(c+1,c+1+len,w[i])-c;
ys[t]=w[i];
w[i]=t;
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
int ma=-1e18,mi=1e18;
for(int k=i;k<=j;k++){
ma=max(ma,w[k]);
mi=min(mi,w[k]);
}
g[i][j]=a+b*(ys[ma]-ys[mi])*(ys[ma]-ys[mi]);
f[i][j][ma][mi]=0;
}
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int mi=1;mi<=len;mi++){
for(int ma=mi;ma<=len;ma++){
for(int k=i;k<j;k++){
f[i][j][ma][mi]=min(f[i][j][ma][mi],f[i][k][ma][mi]+g[k+1][j]);
f[i][j][ma][mi]=min(f[i][j][ma][mi],f[k+1][j][ma][mi]+g[i][k]);
}
g[i][j]=min(g[i][j],f[i][j][ma][mi]+a+b*(ys[ma]-ys[mi])*(ys[ma]-ys[mi]));
int t1=max(w[j+1],ma);
int t2=min(w[j+1],mi);
f[i][j+1][t1][t2]=min(f[i][j+1][t1][t2],f[i][j][ma][mi]);
}
}
}
}
printf("%lld",g[1][n]);
return 0;
}
心得
DP题往往状态是关键，需要勤加练习，见多识广，才能在考场上得出正解，另外转移方程式也很难想，勤加练习。
考试心得
将基础的\(A,B\)题做到极致（\(AC\)），后面的题打暴力分，最后的分数一定会很好看。
——————邱翔宇