A. D1T1
暴力枚举两层的状态，复杂度似乎有点高。
所以显然轮廓线$dp$，将逐层的转移优化为逐个的转移，所以复杂度只有$O(n^2*3^n)$。
当你脑子不想动的时候，请选择大力分类讨论。
然后就会因为少讨论一句话而挂掉90分，并且检查半个小时才查出来。
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 const int inf=0x3f3f3f3f;
6 int n,m;
7 int v[20][20],bin[20];
8 char s[20][20];
9 struct HashMap{
10 const static int p=1050000;
11 int top;
12 int val[p],stack[p];
13 inline int& operator [](int x){
14 return (val[x]^inf)?val[x]:val[stack[++top]=x];
15 }
16 inline void clear(){
17 while(top) val[stack[top--]]=inf;
18 }
19 }f[2];
20 inline int turn(int zt,int pos,int x){
21 return ((zt|(3<<bin[pos]))^(3<<bin[pos]))|(x<<bin[pos]);
22 }
23 inline int get(int zt,int pos){
24 return (zt>>bin[pos])&3;
25 }
26 int main(){
27 scanf("%d%d",&n,&m);
28 for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
29 for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&v[i][j]);
30 for(int i=1;i<=15;++i) bin[i]=i-1<<1;
31 memset(f[0].val,0x3f,sizeof(f[0].val));
32 memset(f[1].val,0x3f,sizeof(f[1].val));
33 int cur=0,zt=0;
34 for(int i=1;i<=m;++i) zt=turn(zt,i,1);
35 f[cur][zt]=0;
36 for(int i=1;i<=n;++i){
37 for(int j=1;j<=m;++j){
38 f[cur^=1].clear();
39 for(int k=1;k<=f[cur^1].top;++k){
40 int zt=f[cur^1].stack[k],val=f[cur^1][zt];
41 if(j==1){
42 int a=get(zt,1);
43 if(s[i][j]^48){
44 if(a==0) f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
45 if(a==1){
46 f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
47 f[cur][turn(zt,j,1)]=min(f[cur][turn(zt,j,1)],val);
48 }
49 if(a==2){
50 f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
51 f[cur][turn(zt,j,1)]=min(f[cur][turn(zt,j,1)],val);
52 }
53 }
54 else{
55 if(a==0) f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
56 if(a==1){
57 f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
58 f[cur][turn(zt,j,0)]=min(f[cur][turn(zt,j,0)],val);
59 }
60 if(a==2){
61 f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
62 f[cur][turn(zt,j,1)]=min(f[cur][turn(zt,j,1)],val);
63 }
64 }
65 }
66 else{
67 int a=get(zt,j-1),b=get(zt,j);
68 if(s[i][j]^48){
69 if(b==0){
70 if(a==0) f[cur][turn(turn(zt,j-1,1),j,2)]=min(f[cur][turn(turn(zt,j-1,1),j,2)],val+v[i][j]);
71 else f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
72 }
73 if(b==1){
74 f[cur][turn(zt,j,1)]=min(f[cur][turn(zt,j,1)],val);
75 if(a==0) f[cur][turn(turn(zt,j-1,1),j,2)]=min(f[cur][turn(turn(zt,j-1,1),j,2)],val+v[i][j]);
76 else f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
77 }
78 if(b==2){
79 f[cur][turn(zt,j,1)]=min(f[cur][turn(zt,j,1)],val);
80 if(a==0) f[cur][turn(turn(zt,j-1,1),j,2)]=min(f[cur][turn(turn(zt,j-1,1),j,2)],val+v[i][j]);
81 else f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
82 }
83 }
84 else{
85 if(b==0){
86 if(a==0) f[cur][turn(turn(zt,j-1,1),j,2)]=min(f[cur][turn(turn(zt,j-1,1),j,2)],val+v[i][j]);
87 else f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
88 }
89 if(b==1){
90 if(a==2) f[cur][turn(zt,j,1)]=min(f[cur][turn(zt,j,1)],val);
91 else f[cur][turn(zt,j,0)]=min(f[cur][turn(zt,j,0)],val);
92 if(a==0) f[cur][turn(turn(zt,j-1,1),j,2)]=min(f[cur][turn(turn(zt,j-1,1),j,2)],val+v[i][j]);
93 else f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
94 }
95 if(b==2){
96 f[cur][turn(zt,j,1)]=min(f[cur][turn(zt,j,1)],val);
97 if(a==0) f[cur][turn(turn(zt,j-1,1),j,2)]=min(f[cur][turn(turn(zt,j-1,1),j,2)],val+v[i][j]);
98 else f[cur][turn(zt,j,2)]=min(f[cur][turn(zt,j,2)],val+v[i][j]);
99 }
100 }
101 }
102 }
103 }
104 }
105 const int lim=1<<m;
106 int ans=inf;
107 for(int i=0;i<lim;++i){
108 int zt=0;
109 for(int j=1;j<=m;++j) zt=turn(zt,j,((i>>j-1)&1)+1);
110 ans=min(ans,f[cur][zt]);
111 }
112 printf("%d\n",ans);
113 return 0;
114 }
D1T1
B. D1T2
发现直接统计似乎有些困难。
正确的方法是将所有的数按照$value$值从大到小排序，
于是已经在序列里的数一定满足$value$大于等于该数。
可以根据当前数的$key$值，判断可以插入在什么位置，于是方案数是简单的。
对于最优方案：
每步贪心地把数插入到使字典序最优的位置，会使答案更优。
所以每步只要找到范围内$key$值大于等于插入元素的第一个元素，如果不存在，那么插在范围的最后。
暴力做这个过程，复杂度是$O(n^2)$的。
一个可行的优化是平衡树，按插入的序列建树。
维护平衡树每个节点子树$key$值的最大值，每次询问只要先分裂出可行的区间，
在平衡树上二分就可以做到$O(logn)$找到最优位置，然后可以在最优位置后插入当前的数。
C. D1T3
显然先跑最短路，求出
从点$1$出发，走$j$条$x$边，到$i$的最短路。
从点$n$出发，走$j$条$x$边，到$i$的最短路。
同时有从点$1$出发，走$j$条$x$边，到$n$的最短路。
枚举当前考虑的点$i$，
那么可以对上述三种最短路维护维护出三个凸包。
对凸包上的交点进行归并排序，可以得出一段$x$取值范围内的最优解。
通过三条直线，可以算得合法的$x$的坐标，判断$x$是否在该范围内即可。
然而我$wa90$必死，已弃。