http://vjudge.net/contest/view.action?cid=51211#overview

花了好长时间了，终于把这个专题做了绝大部分了

A：HDU 3853

最简单的概率DP求期望，从终点推到起点就是了，注意一个坑就是如果p1=1那么他一旦到达这个点，那么就永远走不出去了

题解

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e9

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 double p1[MAXN][MAXN], p2[MAXN][MAXN], p3[MAXN][MAXN], dp[MAXN][MAXN];

 int main()

 {

     int R, C;

     while(~scanf("%d %d", &R, &C))

     {

         for(int i=;i<=R;i++)

             for(int j=;j<=C;j++)

                 scanf("%lf%lf%lf", &p1[i][j], &p2[i][j], &p3[i][j]);

         mem0(dp);

         for(int i=R;i>=;i--)

             for(int j=C;j>=;j--)

             {

                 if(i==R && j==C) continue;

                 if(fabs(p1[i][j] - ) < eps) continue;

                 dp[i][j] = (dp[i][j+]*p2[i][j] + dp[i+][j]*p3[i][j] + ) / (-p1[i][j]) ;

             }

         printf("%.3lf\n", dp[][]);

     }

     return ;

 }

B:HDU 3920

状态压缩DP  题解

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e9

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int T, N;

 typedef double Point[];

 Point st, p[MAXN];

 double dis[MAXN][MAXN], d[MAXN], dp[<<];

 double calc(Point a, Point b)

 {

     double x = a[] - b[];

     double y = a[] - b[];

     return sqrt(x*x + y*y);

 }

 void getDis()

 {

     for(int i=;i<N;i++)

     {

         d[i] = calc(st, p[i]);

         for(int j=i+;j<N;j++)

         {

             dis[j][i] = dis[i][j] = calc(p[i], p[j]);

         }

     }

 }

 int main()

 {

     int t = ;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%lf %lf", &st[], &st[]);

         scanf("%d", &N);

         N <<= ;

         for(int i=;i<N;i++)

             scanf("%lf %lf", &p[i][], &p[i][]);

         getDis();

         dp[] = ;

         for(int i=;i<(<<N);i++) dp[i] = INF;

         queue<int>q;

         q.push();

         while(!q.empty())

         {

             int now = q.front(); q.pop();

             int f=, r;

             while( now & (<<f)  && f < N)

                 f++;

             for(r = f + ; r < N; r ++ )

                 if(!(now & (<<r)))

             {

                 int next = now | (<<f) | (<<r);

                 double minDis = MIN(d[f], d[r]) + dis[f][r];

                 if( fabs(dp[next] - INF) < eps )

                 {

                     q.push(next);

                     dp[next] = dp[now] + minDis;

                 }

                 else if( dp[now] + minDis < dp[next] )

                     dp[next] = dp[now] + minDis;

             }

         }

         printf("Case #%d: %.2lf%\n", ++t, dp[(<<N)-]);

     }

     return ;

 }

C:HDU 1520

简单的树形DP  题解

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e9

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int N, a[MAXN], dp[MAXN][];

 int fa[MAXN];

 vector<int>e[MAXN];

 void DFS(int u)

 {

     int s0 = , s1 = ;

     for(int i=;i<e[u].size();i++)

     {

         DFS(e[u][i]);

         s0 += MAX( dp[e[u][i]][], dp[e[u][i]][] );

         s1 += dp[e[u][i]][];

     }

     dp[u][] = s0;

     dp[u][] = s1 + a[u];

 }

 int main()

 {

     //FOPENIN("in.txt");

     while(~scanf("%d", &N))

     {

         mem0(dp);

         for(int i=;i<=N;i++)

         {

             scanf("%d", &a[i]);

             fa[i] = i;

             e[i].clear();

         }

         int x, y;

         while(scanf("%d %d", &x, &y) && (x||y) ){

             e[y].push_back(x);

             fa[x] = y;

         }

         int ans = ;

         for(int i=;i<=N;i++) if(fa[i] == i)

         {

             DFS(i);

             ans += MAX(dp[i][], dp[i][]);

         }

         printf("%d\n", ans);

     }

     return ;

 }

D:HDU 4284

状态压缩DP  题解

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e8

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int T, N, M, H, Money;

 int dis[MAXN][MAXN], add[MAXN], cost[MAXN];

 int citys[], dp[<<][];

 void init()

 {

     int u, v, w, c, a;

      mem0(add); mem0(cost);mem1(dp);

     scanf("%d %d %d", &N, &M, &Money);

     for(int i = ; i <= N ;i ++ )

     {

         dis[i][i] = ;

         for(int j = ; j <= N ; j ++ )

             if(i != j) dis[i][j] = INF;

     }

     for(int i = ; i < M; i ++ )

     {

         scanf("%d %d %d", &u, &v, &w);

         dis[u][v] = dis[v][u] = MIN(dis[u][v], w);

     }

     scanf("%d", &H);

     for(int i = ; i <= H; i ++ )

     {

         scanf("%d %d %d", &u, &a, &c);

         citys[i] = u;

         add[i] = a;

         cost[i] = c;

     }

 }

 void floyd()

 {

     for(int k=;k<=N;k++)

     for(int i=;i<=N;i++)

     for(int j=;j<=N;j++)

     {

         dis[i][j] = MIN(dis[i][j], dis[i][k] + dis[k][j]);

     }

 }

 int main()

 {

     //FOPENIN("in.txt");

     while(~scanf("%d", &T)) while(T--)

     {

         init();

         floyd();

         int ans = -INF; H += ;

         citys[] = ; cost[] = add[] = ;

         dp[][] = Money;

         for(int now = ; now < (<<H); now ++ )

         {

             for(int u = ; u < H; u ++ ) if(dp[now][u] != -)

             {

                 for(int v = ; v < H; v ++ ) if( (now & (<<v)) ==  )

                 {

                     int next = now | (<<v);

                     if(dp[now][u] >= dis[citys[u]][citys[v]] + cost[v] )

                     {

                         dp[next][v] = MAX(dp[now | (<<v)][v], dp[now][u] - dis[citys[u]][citys[v]] - cost[v] + add[v]);

                     }

                     if(next == (<<H) - )

                     {

                         ans = MAX(ans, dp[next][v]);

                     }

                 }

             }

         }

        //printf("%d\n", ans);

         printf("%s\n", ans >=  ? "YES" : "NO");

     }

     return ;

 }

E:HDU 2196

比较好的题目了，两次DFS，求树上任意点触发的最长距离 题解

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e8

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int N;

 int head[MAXN], next[MAXM], tot;

 int  u[MAXM], v[MAXM], w[MAXM];

 int fir[MAXN], sec[MAXN], ans[MAXN];

 void addEdge(int U, int V, int W)

 {

     u[tot] = U;

     v[tot] = V;

     w[tot] = W;

     next[tot] = head[U];

     head[U] = tot;

     tot ++;

 }

 int dfs1(int x, int fa)

 {

     fir[x] = sec[x] = ;

     for(int e = head[x]; e != -; e = next[e]) if(v[e] != fa)

     {

         int dis = dfs1(v[e], x) + w[e];

         if(dis >= fir[x]) { sec[x] = fir[x]; fir[x] = dis; }

         else if(dis > sec[x]) sec[x] = dis;

     }

     return fir[x];

 }

 void dfs2(int x, int fa, int dis)

 {

     ans[x] = MAX(fir[x], dis);

     for(int e = head[x]; e != -; e = next[e]) if(v[e] != fa)

     {

         int y = v[e];

         if(fir[y] + w[e] == fir[x])

             dfs2(y, x, MAX( dis, sec[x]) + w[e] );

         else

             dfs2(y, x, MAX( dis, fir[x]) + w[e] );

     }

 }

 int main()

 {

     while(~scanf("%d", &N))

     {

         tot = ;

         mem1(head);

         int V, W;

         for(int i = ; i <= N; i ++)

         {

             scanf("%d %d", &V, &W);

             addEdge(i, V, W);

             addEdge(V, i, W);

         }

         dfs1(, );

         dfs2(, , );

         for(int i = ; i <= N; i ++ )

             printf("%d\n", ans[i]);

     }

     return ;

 }

F:HDU 4539

最原始最薄里的状压DP  题解

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e8

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int N, M;

 int ma[];

 int dp[][][];

 int stNum;

 int st[], num[];

 int judge(int x)

 {

     if(x & (x<<)) return ;

     return ;

 }

 int get1(int x)

 {

     int ret = ;

     while(x)

     {

         ret += x & ;

         x >>= ;

     }

     return ret;

 }

 void init()

 {

     mem1(dp);mem0(ma);

     stNum = ;

     for(int i=;i<(<<M);i++) if(judge(i))

     {

         st[stNum] = i;

         num[stNum++] = get1(i);

     }

 }

 int main()

 {

     //FOPENIN("in.txt");

     while(~scanf("%d %d%*c", &N, &M))

     {

         init();

         int x, cur = ;

         for(int i=;i<=N;i++)

             for(int j=;j<M;j++) {

                 scanf("%d", &x);

                 if(x==) ma[i] |= (<<j);

             }

         for(int i=;i<stNum;i++) {

             if(st[i] & ma[]) continue;

             dp[cur][i][] = num[i];

         }

         for(int r = ; r <= N; r ++)

         {

             cur = !cur;

             for(int i = ; i < stNum; i ++)

             {

                 if(st[i] & ma[r]) continue;

                 for(int j = ; j < stNum; j ++ )

                 {

                     if(st[j] & ma[r-]) continue;

                     int p = (st[i]<<) | (st[i]>>);

                     if(st[j] & p) continue;

                     for(int k = ; k < stNum; k ++) if(dp[!cur][j][k] != -)

                     {

                         int pp = st[i] | ((st[j]<<) | (st[j]>>));

                         if(st[k] & pp) continue;

                         dp[cur][i][j] = MAX(dp[cur][i][j], dp[!cur][j][k] + num[i]);

                     }

                 }

             }

         }

         int ans = ;

         for(int i=;i<stNum;i++) for(int j=;j<stNum;j++)

             ans = MAX(ans, dp[cur][i][j]);

         printf("%d\n", ans);

     }

     return ;

 }

 /*

 6

 3

 2

 12

 */

G:HDU 4035

推公式很重要，是看别人做的。。。。题解

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e8

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int T, N;

 vector<int>v[MAXN];

 double k[MAXN], e[MAXN];

 double A[MAXN], B[MAXN], C[MAXN];

 void init()

 {

     int U, V;

     scanf("%d", &N);

     for(int i=;i<=N;i++) v[i].clear();

     for(int i=;i<N-;i++)

     {

         scanf("%d %d", &U, &V);

         v[U].push_back(V);

         v[V].push_back(U);

     }

     for(int i=;i<=N;i++)

     {

         scanf("%d %d", &U, &V);

         k[i] = (double)U / 100.0;

         e[i] = (double)V / 100.0;

     }

 }

 bool DFS(int x, int fa)

 {

     A[x] = k[x];

     B[x] = ( - k[x] - e[x]) / v[x].size();

     C[x] =  - k[x] - e[x];

     if(v[x].size() ==  && x != fa)

         return true;

     double temp = ;

     for(int i = ; i < v[x].size() ; i ++ )

     {

         int y = v[x][i];

         if(y == fa) continue;

         if(!DFS(y, x)) return false;

         A[x] += A[y] * B[x];

         C[x] += C[y] * B[x];

         temp += B[y] * B[x];

     }

     if(fabs(temp - 1.0) < eps) return false;

     A[x] = A[x] / ( - temp);

     B[x] = B[x] / ( - temp);

     C[x] = C[x] / ( - temp);

     return true;

 }

 int main()

 {

     //FOPENIN("in.txt");

     scanf("%d", &T);

     for(int t = ; t <= T; t ++ )

     {

         init();

         if( DFS(, ) && fabs(A[] - 1.0) > eps )

         {

             printf("Case %d: %lf\n", t, C[] / ( - A[]));

         }

         else

         {

             printf("Case %d: impossible\n", t);

         }

     }

 }

I:HDU 1561

树形DP，注意状态转化的过程  题解

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF ((LL)100000000000000000)

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 int dx[] = {-, , , };

 int dy[] = {, -, , };

 int N, M;

 int G[MAXN][MAXN], vis[MAXN], num[MAXN];

 int DP[MAXN][MAXN], D[MAXN];

 void DFS(int u)

 {

     vis[u] = ;

     DP[u][] = num[u];

     for(int i=;i<=N;i++)  if(G[u][i])

     {

         if(!vis[i]) DFS(i);

         for(int j=M;j>;j--)//这里为了保证是先从父节点更新，需要逆序

             for(int k=;k<j;k++)//k<j保证父节点不会被更新掉

                 DP[u][j] = MAX(DP[u][j], DP[u][j-k] + DP[i][k]);

     }

 }

 int main()

 {

     //FOPENIN("in.txt");

     while(~scanf("%d %d", &N, &M) &&( N||M))

     {

         int a;mem0(G);mem0(D);mem0(vis);mem0(DP);

         for(int i=;i<=N;i++) {

             scanf("%d %d", &a, &num[i]);

             if(a != )G[a][i] = ;

             else D[i] = ;

         }

         for(int i=;i<=N;i++) if(!vis[i]){

             DFS(i);

             if(D[i]) for(int j=M;j>=;j--)//同样需要逆序，可以取到0

             {

                 for(int k=;k<=j;k++)

                     DP[][j] = MAX(DP[][j], DP[][j-k] + DP[i][k]);

             }

         }

         printf("%d\n", DP[][M]);

     }

     return ;

 }

J:HDU 4870

1。高斯消元的做法

2。公式推倒很重要

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF ((LL)100000000000000000)

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 double t[];

 int main()

 {

     //FOPENIN("in.txt");

     double p;

     while(~scanf("%lf", &p))

     {

         t[] = ;

         t[] =  / p;

         t[] =  / p +  / p / p;

         for(int i=;i<=;i++)

         {

             t[i] =  / p * t[i-] +  / p - (-p) / p * t[i-];

         }

         double ans =  *t[] + t[] - t[];

         printf("%lf\n", ans);

     }

     return ;

 }

K:POJ 1160

我就喜欢暴力求解  题解

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 100000000

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN ( T a, T b ) { return a < b;   }

 template<class T> T CMP_MAX ( T a, T b ) { return a > b;   }

 template<class T> T MAX ( T a, T b ) { return a > b ? a : b; }

 template<class T> T MIN ( T a, T b ) { return a < b ? a : b; }

 template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; }

 template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b;       }

 template<class T> T SWAP( T& a, T& b ) { T t = a; a = b;  b = t; }

 //typedef __int64 LL;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 int V, P;

 int x[], DP[][][];

 int dis[][], pre[];

 void initDis()

 {

         mem0(dis);mem0(pre);

         for(int i=;i<=V;i++)

         for(int j=i;j<=V;j++)

         for(int k=i;k<=j;k++)

         dis[i][j] += MIN(x[k]-x[i], x[j]-x[k]);

         for(int i=;i<=V;i++)for(int j=i;j>=;j--)

                 pre[i] += x[i] - x[j];

 }

 int main()

 {

         //FOPENIN ( "in.txt" );

        //FOPENOUT("out.txt");

        while(~scanf("%d %d", &V, &P))

        {

                 for(int i=;i<=V;i++)

                         scanf("%d", &x[i]);

                 initDis();

                 for(int i=;i<;i++)

                 for(int j=;j<=MIN(i,P);j++)

                 for(int k=;k<=i;k++){

                         DP[i][j][k] = INF;

                 }

                 int now = ;

                 for(int i=;i<=V;i++)

                 {

                         now = !now;

                         int s = ;

                         for(int j=;j<=i;j++)   DP[now][][j] = pre[j];

                         for(int j=;j<=MIN(i, P); j++)

                         {

                                 DP[now][j][i] = INF;

                                 for(int k=j-;k<i;k++)if(DP[!now][j-][k] != INF)

                                 {

                                         DP[now][j][i] = MIN(DP[now][j][i], DP[now][j-][k] + dis[k][i]);

                                 }

                                 for(int k=j;k<i;k++) DP[now][j][k] = DP[!now][j][k];

                         }

                 }

                 int ans = INF;

                 for(int k=P;k<=V;k++)if(DP[now][P][k] != INF)

                 {

                         int s = ;

                         for(int j = k + ; j <= V; j ++ ) s += x[j] - x[k];

                         ans = MIN(ans, DP[now][P][k] + s);

                 }

                 printf("%d\n", ans);

        }

         return ;

 }

最新文章

  1. 「C语言」int main还是void main？
  2. map vs hash_map
  3. Selenium2学习-013-WebUI自动化实战实例-011-WebElement.getText()值为空问题探索及解决
  4. Oracle角色
  5. 2014 Multi-University Training Contest 10
  6. 「Poetize3」导弹防御塔
  7. C++学习笔记3——类的封装（1）
  8. .call()和.apply()相同点与不同点
  9. Android4.0中蓝牙适配器state machine（状态机）的分析
  10. 使用ServletContext读取properties配置文件
  11. Chrome 里的请求报错 &quot;CAUTION: Provisional headers are shown&quot; 是什么意思?
  12. JS 变量类型互相转换
  13. foreach加循环体与不加循环体的区别
  14. Cisco 4507R+E四引擎VSS故障解决
  15. Bootstrap VS Semantic VS Foundation
  16. struts中指定编码（使用Filter后仍然乱码）
  17. DOM操作案例之--全选与反选
  18. INFINITY的一个坑
  19. 10.05 最初对Linux的了解，对Shell的认识
  20. Hibernate5.1+Sqlserver2000分页查询

热门文章

  1. HDU 1080 Human Gene Functions
  2. windows下github pages + hexo next 搭建个人博客
  3. 集成框架jar包的一些选择
  4. BZOJ 1176 MOKIA
  5. 如何拷贝CMD命令行文本到粘贴板
  6. scala学习笔记(6)：闭包
  7. UML时序图
  8. In App Purchase翻译
  9. js sleep效果
  10. selenium python （十三）对于分页的处理