HDU-4632 

题意：给定一个字符串，长度最长为1000，问该串有多少个回文子串。

分析：设dp[i][j]表示从 i 到 j 有多少个回文子串，则有动态规划方程：

str[i] != str[j]：dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];

str[i]  = str[j]：dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1.

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int mod = 10007;const int N = 1005;char str[N];int f[N][N];int solve(int len) {    memset(f, 0, sizeof (f));    for (int i = 0; i < len; ++i) {        f[i][i] = 1;    }    for (int k = 2; k <= len; ++k) { // 枚举长度         for (int i = 0, j; i < len && (j=i+k-1) < len; ++i) {            if (str[i] == str[j]) {                f[i][j] = (f[i][j-1] + f[i+1][j] + 1) % mod;            } else {                f[i][j] = ((f[i][j-1] + f[i+1][j] - f[i+1][j-1]) % mod + mod) % mod;            }        }    }    return f[0][len-1];}int main() {    int T, ca = 0;    scanf("%d", &T);    while (T--) {        scanf("%s", str);        int len = strlen(str);        printf("Case %d: %d\n", ++ca, solve(len));    }    return 0;    }
          
         
        
       
      

 

HDU-4638 

题意：给定一个序列（1-N的全排列），问任意一个区间内若将所有的数排序后，能够形成多少个不连续的子序列。

分析：对于每一个数字，记录其左边的数字和右边的数字所在的位置，然后根据相互关系维护好一个线段数量的树状数组。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;void getint(int &);struct Node {    int No, l, r;    void read(int _No) {        getint(l), getint(r);        No = _No;    }    bool operator < (const Node &t) const {        return r > t.r;    }};const int N = 100005;int seq[N], pos[N];int n, m;int bit[N];int ans[N];Node e[N];inline int lowbit(int x) {    return x & -x;}void add(int x, int val) {    for (int i = x; i <= n; i+=lowbit(i)) {        bit[i] += val;    }}int sum(int x) {    int ret = 0;    for (int i = x; i > 0; i-=lowbit(i)) {        ret += bit[i];        }    return ret;}void getint(int &t) {    char ch;    while ((ch = getchar()), ch < '0' || ch > '9') ;    t = ch - '0';    while ((ch = getchar()), ch >= '0' && ch <= '9') t = t * 10 + ch - '0';}int main() {    int T;    scanf("%d", &T);    while (T--) {        memset(bit, 0, sizeof (bit));        scanf("%d %d", &n, &m);        for (int i = 1; i <= n; ++i) {            getint(seq[i]);            pos[seq[i]] = i;        }        for (int i = 1; i <= m; ++i) {            e[i].read(i);        }        sort(e+1, e+1+m);        for (int i = n; i >= 1; --i) {            int cnt = 0;            if (seq[i] > 1 && pos[seq[i]-1] > i) ++cnt;            if (seq[i] < n && pos[seq[i]+1] > i) ++cnt;            if (cnt == 0) add(i, 1);            else if (cnt == 2) add(i, -1);        }        int last = n;        for (int i = 1; i <= m; ++i) {            for (int j = last; j > e[i].r; --j) {                if (seq[j] > 1 && pos[seq[j]-1] < j) add(pos[seq[j]-1], 1);                if (seq[j] < n && pos[seq[j]+1] < j) add(pos[seq[j]+1], 1);            }            last = e[i].r;            ans[e[i].No] = sum(e[i].r)-sum(e[i].l-1);        }        for (int i = 1; i <= m; ++i) {            printf("%d\n", ans[i]);        }    }    return 0;    }
          
         
        
       
      

 

HDU-4640 

题意：给定N个点，N最大为17，问从最多3个人从1号点出发到指定的K个点所花的时间最短为多少？（所花时间以到达最后一个点为准）。要求三个人的路线中不能够存在相同的点。

分析：首先通过一次dfs搜索出单个人走出某种状态所需要的最小代价，f[i][j]表示 i 状态到 j 号节点停止的最小花费。这里有一个地方要注意就是记得某个点最后到达 j 点那么也可以由上一个状态最后到达 j 点转移过来，相当于走一个点又返回到原来的位置。紧接着再通过一个dp[i]表示走出 i 状态所需的最小花费，也举是从所有停止点中取出一个最小的，最后再对dp[i]进行一些修正，将其意义变为 i 状态中若存在目标点那么这些点一定要走，而其他的点则可以由该位为空的状态递推过来取一个较小值。这样做的目的是为了后面直接枚举3^n（即将每个点分配给三个人的某一个的组合情况）来得到最终结果，否则的话如果仅仅枚举K个点的情况，那么对于剩下的点又要进行一次讨论，时间复杂度上升了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int inf = 0x3f3f3f3f;int n, m, K, esta;int mp[20][20];int f[1<<17][20]; // f[i][j]表示到达状态i，停在j的最少花费 char vis[1<<17][20];int dp[1<<17];int ret;int dfs(int sta, int e) {    if (vis[sta][e]) return f[sta][e];    vis[sta][e] = 1;    for (int i = 1; i < n; ++i) {        if (i == e) continue;        if ((sta & (1 << i)) && mp[e][i] != inf) {            f[sta][e] = min(f[sta][e], 2*mp[e][i] + dfs(sta^(1<
           
            << n; f[1][0] = 0; // 初始化从第1个节点出发 for (int i = 1; i < LIM; ++i) { for (int j = 0; j < n; ++j) { if (i & (1 << j)) dfs(i, j); } } // 之后处理利用三次机会的组合情况 for (int i = 1; i < LIM; ++i) { for (int j = 0; j < n; ++j) { dp[i] = min(dp[i], f[i][j]); } } for (int i = 1; i < LIM; ++i) { for (int j = 0; j < n; ++j) { if (i & (1 << j) && !(esta & (1<