Ural 1519 Formula 1 插头DP

Ural 1519 Formula 1 插头DP

！！！！！！！！！！！

终于过了插头dp了！

刚刚的爱奇艺！！！！！！！！！！

我以为我这辈子都不会在赛场上过插头dp了！！！！！！！！！！！！！

退役一年多了！！！！！！！！！！！！

还是很激动！！！！！！！！！！！！！！！！！！！！！

2017-5-14！！！！！！！！！！！！！！！！！！！

一名老将的挣扎。

写了三天！终于AC了！

开始的时候无限TLE

然后发现要用hash

然后自己写了hash

然后

然后发现stl很慢..................

然后用别人的

然后WA...................

然后发现要用

然后继续

然后发现不能每次都解码......用类似位运算.........

然后AC！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

自己写代码好艰难......

.我用的括号表示法。。。。。。。

●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz●rz

AC的挫逼代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;#define MAX 0x3f3f3f3f
#define SIZE 1594324const __int64 digit[15] = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969 };
char maps[13][13];
__int64 N, M;//   哈希表
#define LL __int64const int mod = 10007;struct HASH{int head[mod+10], E, next[80000];LL val[80000], cnt[80000];void init() {memset(head, -1, sizeof(head));E = 0;}int findhash(LL x) {return (x%mod + mod)%mod;}void add(LL x, LL sum) {int u = findhash(x);for(int i = head[u];i != -1;i = next[i]) if(val[i] == x) {cnt[i] += sum;return ;}val[E] = x;cnt[E] = sum;next[E] = head[u];head[u] = E++;}}biao1, biao2;//void decode( __int64 code[], __int64 statu ){for( int i = M; i >= 0; i-- ){code[i] = statu / digit[i];statu %= digit[i];}
}int encode( __int64 code[] ){__int64 ans = 0;for( int i = 0; i <= M; i++ ){ans += code[i] * digit[i];}return ans;
}void init(){memset( maps, 0, sizeof( maps ) );for( int i = 1; i <= N; i++ ){scanf( "%s", &maps[i][1] );}
}__int64 solve(){int lasti, lastj;__int64 ans;__int64 code[13];lasti = -1;lastj = -1;int flag = 0;for( int i = N; i >= 1 && !flag; i-- ){for( int j = M; j >= 1 && !flag; j-- ){if( maps[i][j] == '.' ){lasti = i;lastj = j;flag = 1;break;}}}if( lasti == -1 ){return 0;}biao1.init();biao2.init();biao2.add( 0, 1 );ans = 0;for( int i = 1; i <= N; i++ ){biao1.init();for( int k = 0; k < biao2.E; k++ ){__int64 tid, tsum;tid = biao2.val[k];tsum = biao2t[k];biao1.add( tid * 3, tsum );}for( int j = 0; j < M; j++ ){biao2.init();for( int k = 0; k < biao1.E; k++ ){__int64 tid, tsum;tid = biao1.val[k];tsum = biao1t[k];__int64 numj, numj1;numj = ( tid % digit[j+1] ) / digit[j]; numj1 = ( tid % digit[j+2] ) / digit[j+1]; if( maps[i][j+1] == '.' ){if( numj == 0 && numj1 == 0 ){__int64 tt = tid - digit[j] * numj - digit[j+1] * numj1 + digit[j] * 1 + digit[j+1] * 2;if( j + 1 < M ) biao2.add( tt, tsum );}else if( numj == 0 || numj1 == 0 ){int temp = numj + numj1;__int64 tt = tid + digit[j] * temp - digit[j] * numj - digit[j+1] * numj1;biao2.add( tt, tsum );tt = tid - digit[j] * numj - digit[j+1] * numj1 + digit[j+1] * temp;if( j + 1 < M ) biao2.add( tt, tsum );}else{if( numj == 1 && numj1 == 1 ){int temp = 0;int l;for( l = j + 2; l <= M; l++ ){__int64 ttt = tid % digit[l+1] / digit[l];if( ttt == 2 ){if( temp == 0 ){break;}else{temp--;}}else if( ttt == 1 ){temp++;}}if( l <= M ){__int64 ttt = tid % digit[l+1] / digit[l];__int64 tt = tid - digit[j] * numj - digit[j+1] * numj1 + digit[l] * ( 1 - ttt );biao2.add( tt, tsum );}}else if( numj == 2 && numj1 == 2 ){int temp = 0;int l;for( l = j - 1; l >= 0; l-- ){int ttt = tid % digit[l+1] / digit[l];if( ttt == 1 ){if( temp == 0 ){break;}else{temp--;}}else if( ttt == 2 ){temp++;}}if( l >= 0 ){__int64 ttt = tid % digit[l+1] / digit[l];__int64 tt = tid - digit[j] * numj - digit[j+1] * numj1 + digit[l] * ( 2 - ttt );biao2.add( tt, tsum );}}else if( numj == 1 && numj1 == 2 ){__int64 tt = tid - digit[j] * numj - digit[j+1] * numj1;if( i == lasti && j + 1 == lastj && !tt ){biao2.add( tt, tsum );ans += tsum;}}else{__int64 tt = tid - digit[j] * numj - digit[j+1] * numj1;biao2.add( tt, tsum );}}}else{if( numj == 0 && numj1 == 0 ){biao2.add( tid, tsum );}}}biao1 = biao2;	}}return ans;
}int main(){while( scanf( "%d%d", &N, &M ) != EOF ){init();printf( "%I64dn", solve() );}return 0;
}
/*
12 12
............
............
............
............
............
............
............
............
............
............
............
............1076226888605605706
*/