这里写链接内容
刚开始学插头dp好吃力，看了别人的代码有点看不懂，所以就参考了别人的代码，写了注释，希望有帮助 如果看不懂可以问
namespace std;S2 1600000struct Queue{int opt;long long sum;}Q[2][S1];char g[N][N];int pow3[N];//cnt指的是状态有多少种int cnt[2];//state[][j]指的是j这种状态的序号是多少int state[2][S2];int n, m, final, now;(int opt, int col) {return opt / pow3[col] % 3;}(int opt, int col, int value) {return opt + (value – get(opt, col)) * pow3[col];}sum) {//如果是最后一列，且最后一列还有右插头，这就不符合了,第m个存储的是第col列的右插头if (col == m – 1 && get(opt, m))return ;//找出opt这个状态的序号int &id = state[now][opt];//如果拓展过if (id)Q[now][id].sum += sum;else {//没拓展过id = ++cnt[now];Q[now][id].opt = opt;Q[now][id].sum = sum;}}//改变状态，这种情况是论文中的情况2.1int change1(int opt, int i) {for (int flag = 0; i < m; i++) {int tmp = get(opt, i);if (tmp == 1)flag++;else if (tmp == 2)flag–;if (!flag)return set(opt, i, 1);}return -1;}//改变状态，，这种情况是论文中的情况2.2int change2(int opt, int i) {for (int flag = 0; i >= 0; i–) {int tmp = get(opt, i);if (tmp == 2)flag++;else if (tmp == 1)flag–;if (!flag)return set(opt, i, 2);}return -1;}void init() {pow3[0] = 1;for (int i = 1; i < N; i++)pow3[i] = pow3[i – 1] * 3;scanf(“%d%d”, &n, &m);now = 0;for (int i = 0; i < n; i++) {scanf(“%s”, g[i]);for (int j = 0; j < m; j++)if (g[i][j] == ‘.’)final = i * m + j;}enqueue(0,0,1);}void solve() {now ^= 1;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {for (int k = 1, l = cnt[now ^ 1]; k <= l; k++) {int opt = Q[now ^ 1][k].opt;long long sum = Q[now ^ 1][k].sum;int left = get(opt, m), up = get(opt, j);if (g[i][j] == ‘*’) {if (left == 0 && up == 0)enqueue(opt, j, sum);continue;}//论文中的情况1if (left == 0 && up == 0) {enqueue(set(set(opt, m, 2), j, 1), j, sum);}(left == 1 && up == 1) {int tmp = change1(opt, j);enqueue(set(set(tmp, m, 0), j, 0), j, sum);}(left == 2 && up == 2) {int tmp = change2(opt, j);enqueue(set(set(tmp, m, 0), j, 0), j, sum);}(left == 1 && up == 2) {if (i * m + j == final)enqueue(set(set(opt, m, 0), j, 0), j, sum);}(left == 2 && up == 1) {enqueue(set(set(opt, m, 0), j, 0), j, sum);} (left == 0 || up == 0) {enqueue(set(set(opt, m, 0), j, left + up), j, sum);enqueue(set(set(opt, j, 0), m, left + up), j, sum);}}now ^= 1;for(int k = 1, t = cnt[now]; k <= t; k++)state[now][Q[now][k].opt] = 0;cnt[now] = 0;}printf(“%lld\n”, Q[now ^ 1][state[now ^ 1][0]].sum);}int main() {init();solve();return 0;}
你是自由的，不仅是身体上的自由，
