【HDOJ】3386 Final Kichiku “Lanlanshu”

数位DP。
需要注意的是需要特殊处理前导0,另外连续的==匹配,不要计重了,尽量贪心的匹配掉。

 /* 3886 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int mod = ;
const int maxl = ;
const int maxn = ;
char ps[maxl], ps_[maxl];
char sa[maxl], sb[maxl];
int a[maxl], plen;
int dp[maxl][maxn][][];
bool dp_[maxl][maxn]; void f(char *s, int& l) {
int len = strlen(s);
int i = ; l = ;
while (i<len- && s[i]=='')
++i;
while (i < len) {
s[l++] = s[i++]-'';
}
s[l] = '\0';
} bool check(char ch, int d, int dd) {
if (ch == '/')
return d < dd;
if (ch == '-')
return d == dd;
if (ch == '\\')
return d > dd;
return false;
} bool judge(char *s, int len) {
if (len== || check(ps[], s[], s[])==false)
return false; memset(dp_, false, sizeof(dp_));
dp_[][] = true; rep(j, , plen) {
rep(i, , len-) {
if (!dp_[j][i])
continue; if (check(ps[j], s[i], s[i+]))
dp_[j][i+] = true;
if (check(ps[j+], s[i], s[i+]))
dp_[j+][i+] = true;
}
} return dp_[plen][len-];
} int cal(char *s, int len) {
if (len <= )
return ; memset(dp, -, sizeof(dp));
rep(k, , s[]) {
rep(kk, , ) {
if (k == ) {
if (dp[][][][kk] == -)
dp[][][][kk] = ;
else
++dp[][][][kk];
continue;
} if (check(ps[], k, kk)) {
if (dp[][][][kk] == -)
dp[][][][kk] = ;
else
++dp[][][][kk];
}
}
}
rep(kk, , s[]+) {
int at = kk==s[];
if (check(ps[], s[], kk)) {
if (dp[][][at][kk] == -)
dp[][][at][kk] = ;
else
++dp[][][at][kk];
}
} rep(i, , plen+) {
int ii = i + ;
rep(j, , len-) {
int jj = j + ; // consider boundary
if (dp[i][j][][s[j]] >= ) {
rep(k, , s[j+]+) {
int at = k==s[j+]; if (check(ps[ii], s[j], k)) {
if (dp[ii][jj][at][k] >= ) {
dp[ii][jj][at][k] = (dp[ii][jj][at][k] + dp[i][j][][s[j]]) % mod;
} else {
dp[ii][jj][at][k] = dp[i][j][][s[j]];
}
} else if (check(ps[i], s[j], k)) {
if (dp[i][jj][at][k] >= ) {
dp[i][jj][at][k] = (dp[i][jj][at][k] + dp[i][j][][s[j]]) % mod;
} else {
dp[i][jj][at][k] = dp[i][j][][s[j]];
}
}
}
} // consider < boundary
rep(k, , ) {
if (dp[i][j][][k] < )
continue;
rep(kk, , ) {
if (i == ) {
if (k == ) {
if (dp[i][jj][][kk] >= ) {
dp[i][jj][][kk] = (dp[i][jj][][kk] + dp[i][j][][k]) % mod;
} else {
dp[i][jj][][kk] = dp[i][j][][k];
}
} else {
if (check(ps[ii], k, kk)) {
if (dp[ii][jj][][kk] >= ) {
dp[ii][jj][][kk] = (dp[ii][jj][][kk] + dp[i][j][][k]) % mod;
} else {
dp[ii][jj][][kk] = dp[i][j][][k];
}
}
}
continue;
} if (check(ps[ii], k, kk)) {
if (dp[ii][jj][][kk] >= ) {
dp[ii][jj][][kk] = (dp[ii][jj][][kk] + dp[i][j][][k]) % mod;
} else {
dp[ii][jj][][kk] = dp[i][j][][k];
}
} else if (check(ps[i], k, kk)) {
if (dp[i][jj][][kk] >= ) {
dp[i][jj][][kk] = (dp[i][jj][][kk] + dp[i][j][][k]) % mod;
} else {
dp[i][jj][][kk] = dp[i][j][][k];
}
}
}
}
}
} int ret = ; rep(k, , ) {
if (dp[plen][len-][][k] >= )
ret = (ret + dp[plen][len-][][k]) % mod;
if (dp[plen][len-][][k] >= )
ret = (ret + dp[plen][len-][][k]) % mod;
} return ret;
} void solve() {
int alen, blen;
int ans = , tmp; plen = strlen(ps+);
f(sa, alen);
f(sb, blen); tmp = cal(sb, blen);
ans += tmp;
tmp = cal(sa, alen);
ans -= tmp;
if (judge(sa, alen))
++ans; ans = (ans + mod) % mod;
printf("%08d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif while (scanf("%s", ps+)!=EOF) {
scanf("%s %s", sa, sb);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
上一篇:Java 给 PowerPoint 文档添加背景颜色和背景图片


下一篇:HDU - 1045 Fire Net(二分匹配)