[关闭]
@ivorysi 2018-01-09T01:09:41.000000Z 字数 30698 阅读 899

动态规划学习笔记

笔记

树型dp

BZOJ 1040 骑士

1040: [ZJOI2008]骑士

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 5703 Solved: 2208
[Submit][Status][Discuss]

Description

Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一
些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

Input

第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力
和他最痛恨的骑士。

Output

应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

Sample Input

3
10 2
20 3
30 1

Sample Output

30

HINT

N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。

题解

在基环外向树上选一个权值最大的独立集
我们找到环上的一条边，把这条边中的一个点选成根进行dp，这个时候，根节点的f[rt][0]一定是准确的，但是f[rt][1]是不准确的，我们必须强制这条边的另一个点不选，然后将这个状态走环一圈，再用来更新f[rt][1]
由于每个点的仇恨的人向自己连一条边，那么入度必然是1，我们可以直连单向边，然后记录指向自己的人作为父亲，每个点顺着父亲走必然可以走到环上

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MAXN 1000005
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. struct node {
  10.     int to,next;
  11. }edge[MAXN];
  12. int head[MAXN],sumedge,fa[MAXN],n;
  13. ll val[MAXN],ans,f[MAXN][2];
  14. bool vis[MAXN],cnt[MAXN];
  15. void add(int u,int v) {
  16.     edge[++sumedge].to = v;
  17.     edge[sumedge].next = head[u];
  18.     head[u] = sumedge;
  19.     fa[v] = u;
  20. }
  21. void Dfs(int u) {
  22.     vis[u] = 1;
  23.     f[u][1] = val[u];
  24.     for(int i = head[u] ; i ; i = edge[i].next) {
  25.         int v = edge[i].to;
  26.         if(!vis[v]) {
  27.             Dfs(v);
  28.             f[u][0] += max(f[v][1],f[v][0]);
  29.             f[u][1] += f[v][0];
  30.         }
  31.     }
  32. } 
  33. void Dp(int x) {
  34.     int rt;
  35.     for(rt = x ; !cnt[rt] ; rt = fa[rt]) {
  36.         cnt[rt] = 1;
  37.     }
  38.     Dfs(rt);
  39.     x = fa[rt];
  40.     f[x][1] = f[x][0];
  41.     for(x = fa[x] ; x != rt ; x = fa[x]) {
  42.         f[x][1] = val[x];f[x][0] = 0;
  43.         for(int i = head[x] ; i ; i = edge[i].next) {
  44.             int v = edge[i].to;
  45.             f[x][1] += f[v][0];
  46.             f[x][0] += max(f[v][0],f[v][1]);
  47.         }
  48.     }
  49.     f[rt][1] = val[rt];
  50.     for(int i = head[rt] ; i ; i = edge[i].next) {
  51.         int v = edge[i].to;
  52.         f[rt][1] += f[v][0];
  53.     }
  54.     ans += max(f[rt][1],f[rt][0]);
  55. }
  56. int main() {
  57. #ifdef ivorysi
  58.     freopen("f1.in","r",stdin);
  59. #endif
  60.     scanf("%d",&n);
  61.     int u;
  62.     for(int i = 1 ; i <= n ; ++i) {
  63.         scanf("%lld%d",&val[i],&u);
  64.         add(u,i);
  65.     }
  66.     for(int i = 1 ; i <= n ; ++i) {
  67.         if(!vis[i]) Dp(i);
  68.     }
  69.     printf("%lld\n",ans);   
  70. }

BZOJ 1023 1023: [SHOI2008]cactus仙人掌图

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3092 Solved: 1285
[Submit][Status][Discuss]

Description

如果某个无向连通图的任意一条边至多只出现在一条简单回路（simplevcycle）里，我们就称这张图为仙人掌图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。
举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两
个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径。

Input

输入的第一行包括两个整数n和m（1≤n≤50000以及0≤m≤10000）。其中n代表顶点个数，我们约定图中的顶
点将从1到n编号。接下来一共有m行。代表m条路径。每行的开始有一个整数k（2≤k≤1000），代表在这条路径上
的顶点个数。接下来是k个1到n之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边
。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从3经过8，又从8返回到了3，但是我们
保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。

Output

只需输出一个数，这个数表示仙人图的直径长度。

Sample Input

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10 8

10 1
10 1 2 3 4 5 6 7 8 9 10

Sample Output

8

9

HINT

对第一个样例的说明：如图，6号点和12号点的最短路径长度为8，所以这张图的直径为8。
【注意】使用Pascal语言的选手请注意：你的程序在处理大数据的时候可能会出现栈溢出。
如果需要调整栈空间的大小，可以在程序的开头填加一句：{$M5000000}，其中5000000即指代栈空间的大小，请根据自己的程序选择适当的数值。

题解

同学们今天我们来学习仙人掌！
唉我好菜啊啥都不会
一个树上直径是很简单的，但是仙人掌的直径呢
还有啊……仙人掌这个东西怎么找环呢，想一想就好麻烦好麻烦啊
其实没有那么麻烦，于是我决定先写仙人掌怎么找环
一个最干枯的仙人掌是一棵树，于是我们决定把仙人掌当树来遍历，能构成环的边，必然就是一条从儿子指向祖先的回边，那么这个东西就是一个环
……是不是很像Tarjan求双连通分量
可我双连通分量都没学好啊qwq
由于仙人掌在环与环链接的东西就是桥，咦咦咦好像这个桥和Tarjan求桥的算法差不多？？？
然后我们关于如何找环的问题（似乎是）很明朗了，我们只要深搜出一棵dfs搜索树，记录dfn和low，深搜的时候不断更新，记录父亲和深度，然后如果没有这条边指向的点回不到这个点，那么可以用它下面的仙人掌来更新答案

有一个环的树就是基环外向树了，我们认为环上的树根都是等价的，我们可以断环为链，认为这条链上有很多树根，我们用它们彼此转移来更新答案

之后，选一个在搜索树里深度最小的点作为代表节点（因为只有这个点还和上面的点有联系啦！）用环上的东西更新它的最长路

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MAXN 50005
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. struct node {
  10.     int to,next;
  11. }edge[MAXN * 20];
  12. int head[MAXN],sumedge,n,m,ans,f[MAXN],tot,que[MAXN * 2],sq[MAXN * 2];
  13. int dfn[MAXN],low[MAXN],inx,deep[MAXN],fa[MAXN];
  14. void add(int u,int v) {
  15.     edge[++sumedge].to = v;
  16.     edge[sumedge].next = head[u];
  17.     head[u] = sumedge;
  18. }
  19. void addtwo(int u,int v) {
  20.     add(u,v);add(v,u);
  21. }
  22. void Dp(int root,int x) {
  23.     tot = deep[x] - deep[root] + 1;
  24.     for(int k = x ; k != root ; k = fa[k]) {
  25.         sq[tot--] = f[k];
  26.     }
  27.     sq[tot] = f[root];
  28.     tot = deep[x] - deep[root] + 1;
  29.     for(int i = 1 ; i <= tot; ++i) sq[i + tot] = sq[i];
  30.     int ql,qr;
  31.     que[ql = qr = 1] = 1;
  32.     for(int i = 2 ; i <= 2 * tot ; ++i) {
  33.         while(ql <= qr && i - que[ql] > tot / 2) ql++;
  34.         if(ql <= qr) ans = max(ans,sq[i] + sq[que[ql]] + i - que[ql]);
  35.         while(ql <= qr && sq[que[qr]] - que[qr] <= sq[i] - i) --qr;
  36.         que[++qr] = i;
  37.     }
  38.     for(int i = 2 ; i <= tot ; ++i) {
  39.         f[root] = max(f[root],sq[i] + min(i - 1,tot - i + 1));
  40.     }
  41. }
  42. void Dfs(int u) {
  43.     dfn[u] = low[u] = ++inx;
  44.     for(int i = head[u] ; i ; i =edge[i].next) {
  45.         int v = edge[i].to;
  46.         if(v != fa[u]) {
  47.             if(!dfn[v]) {
  48.                 fa[v] = u;
  49.                 deep[v] = deep[u] + 1;
  50.                 Dfs(v);
  51.                 low[u] = min(low[u],low[v]);
  52.             }
  53.             else low[u] = min(dfn[v],low[u]);
  54.             if(low[v] > dfn[u]) {//这个是>号，因为要求桥
  55.                 ans = max(f[u] + f[v] + 1,ans);
  56.                 f[u] = max(f[u],f[v] + 1);
  57.             }
  58.         }
  59.     }
  60.     for(int i = head[u] ; i ; i = edge[i].next) {
  61.         int v = edge[i].to;
  62.         if(fa[v] != u && dfn[v] > dfn[u]) {
  63.             Dp(u,v);
  64.         }
  65.     }
  66. }
  67. int main() {
  68. #ifdef ivorysi
  69.     freopen("f1.in","r",stdin);
  70. #endif
  71.     scanf("%d%d",&n,&m);
  72.     int k,a,b;
  73.     for(int i = 1 ; i <= m ; ++i) {
  74.         scanf("%d%d",&k,&a);
  75.         for(int j = 2 ; j <= k ; ++j) {
  76.             scanf("%d",&b);
  77.             addtwo(a,b);a = b;
  78.         }
  79.     }
  80.     deep[1] = 1;
  81.     Dfs(1);
  82.     printf("%d\n",ans);
  83. }

BZOJ 1030: [JSOI2007]文本生成器

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 5473 Solved: 2267
[Submit][Status][Discuss]

Description

JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文
章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的
标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？

Input

输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包
含英文大写字母A..Z

Output

一个整数，表示可能的文章总数。只需要知道结果模10007的值。

Sample Input

2 2
A
B

Sample Output

100

题解

正难则反，转化为求不出现这些单词的串的个数
建出AC自动机来，然后标记上所有危险节点，然后再安全图上dp
最后用 - 每个点的答案总和

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MOD 10007
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. struct node {
  10.     int next[26],prev;
  11.     bool danger;
  12. }tr[60005];
  13. int n,m,nodecnt;
  14. int ans,que[60005],f[60005][105],ql,qr;
  15. char s[1005];
  16. void Insert() {
  17.     int p = 1;
  18.     int len = strlen(s + 1);
  19.     for(int i = 1 ; i <= len ; ++i) {
  20.         int e = s[i] - 'A';
  21.         if(!tr[p].next[e]) tr[p].next[e] = ++nodecnt;
  22.         p = tr[p].next[e]; 
  23.     }
  24.     tr[p].danger = 1;
  25. }
  26. void Build_ACAM() {
  27.     ql = 1;qr = 0;
  28.     tr[1].prev = 1;
  29.     for(int i = 0 ; i < 26 ; ++i) {
  30.         if(!tr[1].next[i]) tr[1].next[i] = 1;
  31.         else {que[++qr] = tr[1].next[i];tr[tr[1].next[i]].prev = 1;}
  32.     }
  33.     while(ql <= qr) {
  34.         int now = que[ql++];
  35.         int k,p;
  36.         p = tr[now].prev;
  37.         for(int i = 0 ; i < 26 ; ++i) {
  38.             k = tr[now].next[i];
  39.             if(k) {
  40.                 tr[k].prev = tr[p].next[i];
  41.                 que[++qr] = k;
  42.             }
  43.             else tr[now].next[i] = tr[p].next[i];
  44.         }
  45.         if(tr[p].danger) tr[now].danger = 1;
  46.     }
  47. }
  48. int main() {
  49. #ifdef ivorysi
  50.     freopen("f1.in","r",stdin);
  51. #endif
  52.     scanf("%d%d",&n,&m);
  53.     ans = 1;
  54.     nodecnt = 1;
  55.     for(int i = 1 ; i <= m ; ++i) ans = ans * 26 % MOD;
  56.     for(int i = 1 ; i <= n ; ++i) {
  57.         scanf("%s",s + 1);
  58.         Insert();
  59.     }
  60.     Build_ACAM();
  61.     f[1][0] = 1;
  62.     for(int j = 1 ; j <= m ; ++j) {
  63.         for(int i = 1 ; i <= nodecnt ; ++i) {
  64.             if(f[i][j - 1] == 0) continue;
  65.             for(int k = 0 ; k < 26 ; ++k) {
  66.                 int to = tr[i].next[k];
  67.                 if(tr[to].danger) continue;
  68.                 f[to][j] += f[i][j - 1];
  69.                 f[to][j] %= MOD;
  70.             }
  71.         }
  72.     }
  73.     for(int i = 1 ; i <= nodecnt ; ++i) {
  74.         ans -= f[i][m];
  75.         ans = (ans % MOD + MOD) % MOD;
  76.     }
  77.     printf("%d\n",ans);
  78. }

区间DP

1068: [SCOI2007]压缩

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1547 Solved: 982
[Submit][Status][Discuss]

Description

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没
有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

Input

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

Output

输出仅一行，即压缩后字符串的最短长度。

Sample Input

bcdcdcdcdxcdcdcdcd

Sample Output

12

HINT

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50

题解

因为前面如果有M就会影响后面的更新，所以我们需要在区间dp上加一维状态表示是否有过M
f[i][j][1]表示可以有M（实际上，如果没有M不影响它的更新）
f[i][j][0]表示不可以有M
更新的时候要么就枚举中间位置，直接把j - k长度的串插在上一次压缩后面
要么合并两个区间，f[i][k][1]和f[k+1][j][1]，这个时候中间必须加一个M才能保证后面的东西不被影响
要么就是长度为偶数的时候压缩一个串

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MOD 10007
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. int f[55][55][2],len;
  10. char s[55];
  11. bool check(int z,int t,int l) {
  12.     for(int i = 0 ;i < l ; ++i) {
  13.         if(s[z + i] != s[t + i]) return false;
  14.     }
  15.     return true;
  16. }
  17. int main() {
  18. #ifdef ivorysi
  19.     freopen("f1.in","r",stdin);
  20. #endif
  21.     scanf("%s",s + 1);
  22.     len = strlen(s + 1);
  23.     for(int i = 1 ; i <= len ; ++i) f[i][i][0]=f[i][i][1]=1;
  24.     for(int l = 1 ; l <= len ; ++l) {
  25.         for(int i = 1 ; i <= len ; ++i) {
  26.             int j = i + l;
  27.             if(j > len) break;
  28.             f[i][j][0] = f[i][j][1] = l + 1;
  29.             for(int k = i ; k < j ; ++k) {
  30.                 f[i][j][0] = min(f[i][j][0],f[i][k][0] + j - k);
  31.                 f[i][j][1] = min(f[i][j][1],f[i][k][1] + j - k);
  32.                 f[i][j][1] = min(f[i][j][1],f[i][k][1] + f[k + 1][j][1] + 1);
  33.             }
  34.             if(l & 1) {
  35.                 int k = i + j + 1 >> 1;
  36.                 if(check(i,k, l + 1 >>1)) {
  37.                     f[i][j][0] = min(f[i][j][0],f[i][k - 1][0] + 1);
  38.                     f[i][j][1] = min(f[i][j][1],f[i][k - 1][0] + 1);
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     printf("%d\n",min(f[1][len][1],f[1][len][0]));
  44. }

BZOJ 1090: [SCOI2003]字符串折叠

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1679 Solved: 1115
[Submit][Status][Discuss]

Description

折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S  S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 3. 如果A  A’, BB’，则AB  A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B)  AAACBB，而2(3(A)C)2(B)AAACAAACBB 给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

Input

仅一行，即字符串S，长度保证不超过100。

Output

仅一行，即最短的折叠长度。

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

14

HINT

一个最短的折叠为：2(NEERC3(YES))

题解

区间f[i][j]表示从i到j最短压缩成多短
枚举中间位置进行区间合并
然后每次枚举一个循环节看看能不能满足，进行更新

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MOD 10007
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. int f[105][105],n;
  10. char s[105];
  11. inline int getbase(int x) {
  12.     if(x <= 9) return 1;
  13.     else if(x <= 99) return 2;
  14.     else return 3;
  15. }
  16. bool check(int st,int ed,int l) {
  17.     for(int i = st + l; i <= ed ; i += l) {
  18.         for(int j = 0 ; j < l ; ++j) {
  19.             if(s[st + j] != s[i + j]) return false;
  20.         }
  21.     }
  22.     return true;
  23. }
  24. int main() {
  25. #ifdef ivorysi
  26.     freopen("f1.in","r",stdin);
  27. #endif
  28.     scanf("%s",s + 1);
  29.     n = strlen(s + 1);
  30.     for(int i = 1 ; i <= n ; ++i) f[i][i] = 1;
  31.     for(int l = 1 ; l <= n ; ++l) {
  32.         for(int i = 1 ; i <= n ; ++i) {
  33.             int j = i + l;
  34.             if(j > n) break;
  35.             f[i][j] = l + 1;
  36.             for(int k = i ; k < j ; ++k) {
  37.                 f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j]);
  38.             }
  39.             for(int z = 1 ; z < l + 1 ; ++z) {
  40.                 if((l + 1) % z == 0) {
  41.                     int t = i + z - 1, k = (l + 1) / z;
  42.                     if(f[i][t] + 2 + getbase(k) > f[i][j]) continue;
  43.                     if(check(i,j,z)) {
  44.                         f[i][j] = f[i][t] + 2 + getbase(k); 
  45.                     }
  46.                 }
  47.             }
  48.         }
  49.     }
  50.     printf("%d\n",f[1][n]);
  51. }

Multiplication Puzzle

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 11403 Accepted: 7068

Description

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.
The goal is to take cards in such order as to minimize the total number of scored points.
For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring
10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000
If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be
1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

Input

The first line of the input contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.

Output

Output must contain a single integer - the minimal score.

Sample Input

6
10 1 50 50 20 5

Sample Output

3650

题解

NOIP傻逼题，怒切
我居然还调了五分钟，太耻辱了

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. //#define ivorysi
  6. using namespace std;
  7. typedef long long ll;
  8. ll f[105][105],n;
  9. ll num[105];
  10. int main() {
  11. #ifdef ivorysi
  12.     freopen("f1.in","r",stdin);
  13. #endif
  14.     scanf("%d",&n);
  15.     for(int i = 1; i <= n ; ++i) scanf("%lld",&num[i]);
  16.     for(int l = 2 ; l <= n ; ++l) {
  17.         for(int i = 1; i <= n ; ++i) {
  18.             int j = i + l;
  19.             if(j > n) break;
  20.             f[i][j] = 100000000000000;
  21.             for(int k = i + 1; k < j ; ++k) {
  22.                 f[i][j] = min(f[i][j],
  23.                     f[i][k] + f[k][j] + num[k] * num[i] * num[j]);
  24.             }
  25.         }
  26.     }
  27.     printf("%lld\n",f[1][n]);
  28. }

HDU 5115 Dire Wolf

Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 2965 Accepted Submission(s): 1765

Problem Description

Dire wolves, also known as Dark wolves, are extraordinarily large and powerful wolves. Many, if not all, Dire Wolves appear to originate from Draenor.
Dire wolves look like normal wolves, but these creatures are of nearly twice the size. These powerful beasts, 8 - 9 feet long and weighing 600 - 800 pounds, are the most well-known orc mounts. As tall as a man, these great wolves have long tusked jaws that look like they could snap an iron bar. They have burning red eyes. Dire wolves are mottled gray or black in color. Dire wolves thrive in the northern regions of Kalimdor and in Mulgore.
Dire wolves are efficient pack hunters that kill anything they catch. They prefer to attack in packs, surrounding and flanking a foe when they can.
— Wowpedia, Your wiki guide to the World of Warcra
Matt, an adventurer from the Eastern Kingdoms, meets a pack of dire wolves. There are N wolves standing in a row (numbered with 1 to N from left to right). Matt has to defeat all of them to survive.
Once Matt defeats a dire wolf, he will take some damage which is equal to the wolf’s current attack. As gregarious beasts, each dire wolf i can increase its adjacent wolves’ attack by bi. Thus, each dire wolf i’s current attack consists of two parts, its basic attack ai and the extra attack provided by the current adjacent wolves. The increase of attack is temporary. Once a wolf is defeated, its adjacent wolves will no longer get extra attack from it. However, these two wolves (if exist) will become adjacent to each other now.
For example, suppose there are 3 dire wolves standing in a row, whose basic attacks ai are (3, 5, 7), respectively. The extra attacks bi they can provide are (8, 2, 0). Thus, the current attacks of them are (5, 13, 9). If Matt defeats the second wolf first, he will get 13 points of damage and the alive wolves’ current attacks become (3, 15).
As an alert and resourceful adventurer, Matt can decide the order of the dire wolves he defeats. Therefore, he wants to know the least damage he has to take to defeat all the wolves.

Input

The first line contains only one integer T , which indicates the number of test cases. For each test case, the first line contains only one integer N (2 ≤ N ≤ 200).
The second line contains N integers ai (0 ≤ ai ≤ 100000), denoting the basic attack of each dire wolf.
The third line contains N integers bi (0 ≤ bi ≤ 50000), denoting the extra attack each dire wolf can provide.

Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1), y is the least damage Matt needs to take.

Sample Input

2
3
3 5 7
8 2 0
10
1 3 5 7 9 2 4 6 8 10
9 4 1 2 1 2 1 4 5 1

Sample Output

Case #1: 17
Case #2: 74
Hint
In the first sample, Matt defeats the dire wolves from left to right. He takes 5 + 5 + 7 = 17 points of damage which is the least damage he has to take.

题解

啊……我……看错题了！！！
我以为是……每次回合都会有加成，结果是，击打一个狼的时候，活着的狼会及时帮助它
所以区间dp枚举最后一个打死的狼就行了！！！
我的天我这个傻逼

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MAXN 205
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. int T;
  10. int n;
  11. ll a[MAXN],b[MAXN],f[MAXN][MAXN];
  13. int main() {
  14. #ifdef ivorysi
  15.     freopen("f1.in","r",stdin);
  16. #endif
  17.     scanf("%d",&T);
  18.     for(int i = 1 ; i <= T ; ++i) {
  19.     printf("Case #%d: ",i);
  20.     scanf("%d",&n);
  21.     for(int j = 1 ; j <= n ; ++j) {
  22.         scanf("%lld",&a[j]);
  23.     }
  24.     for(int j = 1 ; j <= n ; ++j) {
  25.         scanf("%lld",&b[j]);
  26.     }
  27.     for(int l = 0 ; l <= n ; ++l) {
  28.         for(int k = 1 ; k <= n ; ++k) {
  29.         int t = k + l;
  30.         if(t > n) break;
  31.         f[k][t] = 10000000000000000LL;
  32.         for(int z = k ; z<= t ; ++z) {
  33.             f[k][t] = min(f[k][t],f[k][z - 1] + f[z + 1][t] + a[z] + b[k - 1] + b[t + 1]);
  34.         }
  35.         }
  36.     }
  37.     printf("%lld\n",f[1][n]);
  38.     }
  39. }

状压DP

1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4757 Solved: 2760
[Submit][Status][Discuss]

Description

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

方案数。

Sample Input

3 2

Sample Output

16

题解

f[i][j][S]表示前i行放了j个第i行状态为S
我们枚举下一行的状态进行转移
转移的初始化是f[0][0][0] = 1

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MAXN 205
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  10. int n,m;
  11. ll f[10][90][600],ans;
  12. int g[600],t;
  13. int main() {
  14. #ifdef ivorysi
  15.     freopen("f1.in","r",stdin);
  16. #endif
  17.     scanf("%d%d",&n,&m);
  18.     if(m > n*n/3 && m >= n * n) {puts("0");return 0;}
  19.     else {
  20.     t = 1 << n;g[0] = 0;f[0][0][0] = 1;
  21.     for(int i = 1 ; i < t ; ++i) g[i] = g[i >> 1] + (i & 1);
  22.     for(int i = 1 ; i <= n ; ++i) {
  23.         for(int j = 0 ; j < t ; ++j) {
  24.         if(g[j] <= m && !(j & (j << 1))) {
  25.             for(int k = 0 ; k < t ; ++k) {
  26.             if(g[k] <= m && !(k & (k << 1)) && !(k & j) && !(k & (j << 1)) && !((k << 1) & j)) {
  27.                 for(int l = g[k] + g[j] ; l <= m ; ++l) {
  28.                 f[i][l][j] += f[i - 1][l - g[j]][k];
  29.                 }
  30.             }
  31.             }
  32.         }
  33.         }
  34.     }
  35.     }
  36.     for(int i = 0 ; i < t ; ++i) ans += f[n][m][i];
  37.     printf("%lld\n",ans);
  38. }

POJ 3254 Corn Fields

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 17458 Accepted: 9191

Description

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

Line 1: Two space-separated integers: M and N
Lines 2..M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

Sample Input

2 3
1 1 1
0 1 0

Sample Output

9

Hint

Number the squares as follows:
1 2 3
4
There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.

题解

和前面那道题差不多，也是状压dp
然后只要判断没有相邻的边就可以了，四个角就不用考虑了

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MAXN 205
  6. #define MOD 100000000
  7. //#define ivorysi
  8. using namespace std;
  9. typedef long long ll;
  11. int n,m,cnt;
  12. int squ[15][15];
  13. int unable[15];
  14. int f[13][150][1 << 12],t,g[(1<<12) + 3],ans;
  15. int main() {
  16. #ifdef ivorysi
  17.     freopen("f1.in","r",stdin);
  18. #endif
  19.     scanf("%d%d",&n,&m);
  20.     for(int i = 1 ; i <= n ; ++i) {
  21.     for(int j = 1 ; j <= m ; ++j) {
  22.         scanf("%d",&squ[i][j]);
  23.         if(squ[i][j]) ++cnt;
  24.         else unable[i] |= 1 << (j - 1);
  25.     }
  26.     }
  27.     int now = 0;
  28.     f[0][0][0] = 1;
  29.     t = 1 << m;
  30.     for(int i = 1 ; i < t ; ++i) g[i] = g[i >> 1] + (i & 1);
  31.     for(int i = 1 ; i <= n ; ++i) {
  32.     for(int j = 0 ; j < t ; ++j) {
  33.         if(unable[i] & j) continue;
  34.         if(j & (j << 1)) continue;
  35.         for(int k = 0 ; k < t ; ++k) {
  36.         if((k & (k << 1)) || (k & unable[i - 1]) || (k & j)) continue;
  37.         for(int l = g[k] + g[j] ; l <= cnt ; ++l) {
  38.             f[i][l][j] += f[i - 1][l - g[j]][k];
  39.             f[i][l][j] %= MOD;
  40.         }
  41.         }
  42.     }
  43.     }
  44.     for(int l = 0 ; l <= cnt ; ++l) {
  45.     for(int j = 0 ; j < t ; ++j) {
  46.         ans += f[n][l][j];
  47.         ans %= MOD;
  48.     }
  49.     }
  50.     printf("%d\n",ans);
  51. }

BZOJ 2064: 分裂

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 665 Solved: 411
[Submit][Status][Discuss]

Description

背景： 和久必分，分久必和。。。 题目描述： 中国历史上上分分和和次数非常多。。通读中国历史的WJMZBMR表示毫无压力。 同时经常搞OI的他把这个变成了一个数学模型。 假设中国的国土总和是不变的。 每个国家都可以用他的国土面积代替， 又两种可能，一种是两个国家合并为1个，那么新国家的面积为两者之和。 一种是一个国家分裂为2个，那么2个新国家的面积之和为原国家的面积。 WJMZBMR现在知道了很遥远的过去中国的状态，又知道了中国现在的状态，想知道至少要几次操作（分裂和合并各算一次操作），能让中国从当时状态到达现在的状态。

Input

第一行一个数n1，表示当时的块数，接下来n1个数分别表示各块的面积。 第二行一个数n2，表示现在的块，接下来n2个数分别表示各块的面积。

Output

一行一个数表示最小次数。

Sample Input

1 6
3 1 2 3

Sample Output

2

数据范围：

对于100%的数据，n1,n2<=10，每个数<=50
对于30%的数据，n1,n2<=6，

题解

这道题需要emmmm状压dp！
然而我一看题就mengbier
我们考虑一个原始子集对应一个目标子集，由这个子集转化到目标子集，那么所需要的花费是
假设原始子集大小为x，目标子集大小为y
花费是x - 1 + y - 1
那么总共花费就是 n1 + n2 - 2×子集个数
显然子集个数要越多越好
那么问题就转化成，将两个序列划分成最多的子集，使得每个子集总和相等
怎么dp呢，我们记录f[S]为选了几个数，我们处理的时候使得第一个序列里的数为正数，第二个序列里的数为负数
然后枚举S的子集，然而这样会提高复杂度，但是其实我们只需要枚举S里面的元素个数，因为比S少一个元素的子集一定覆盖了之前所有的答案
如果S的总和是0，那么证明可以新加一个对应子集，f[S]++

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. //#define ivorysi
  6. using namespace std;
  7. typedef long long ll;
  9. int n1,n2,n;
  10. int sum[(1 << 20) + 5],f[(1 << 20) + 5],t;
  11. int main() {
  12. #ifdef ivorysi
  13.     freopen("f1.in","r",stdin);
  14. #endif
  15.     scanf("%d",&n1);
  16.     for(int i = 1 ; i <= n1 ; ++i) {
  17.     scanf("%d",&sum[1 << (i - 1)]);
  18.     }
  19.     scanf("%d",&n2);
  20.     for(int i = 1 ; i <= n2 ; ++i) {
  21.     scanf("%d",&sum[1 << (i + n1 - 1)]);
  22.     sum[1 << (i + n1 - 1)] = -sum[1 << (i + n1 - 1)];
  23.     }
  24.     n = n1 + n2;
  25.     t = 1 << n;
  26.     for(int i = 1 ; i < t ; ++i) {
  27.     int k = i & (-i);
  28.     sum[i] = sum[i - k] + sum[k];
  29.     for(int j = 1 ; j <= n ; ++j) {
  30.         if(i & (1 << j - 1)) {
  31.         int h = i - (1 << j - 1);
  32.         if(f[h] > f[i]) f[i] = f[h];
  33.         }
  34.     }
  35.     if(sum[i] == 0) ++f[i];
  36.     }
  37.     printf("%d\n",n - 2 * f[t - 1]);
  38. }

3195: [Jxoi2012]奇怪的道路

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 512 Solved: 333
[Submit][Status][Discuss]

Description

小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达，交通方面也不例外。考古学家已经知道，这个文明在全盛时期有n座城市，编号为1..n。m条道路连接在这些城市之间，每条道路将两个城市连接起来，使得两地的居民可以方便地来往。一对城市之间可能存在多条道路。
据史料记载，这个文明的交通网络满足两个奇怪的特征。首先，这个文明崇拜数字K，所以对于任何一条道路，设它连接的两个城市分别为u和v，则必定满足1 <=|u - v| <= K。此外，任何一个城市都与恰好偶数条道路相连（0也被认为是偶数）。不过，由于时间过于久远，具体的交通网络我们已经无法得知了。小宇很好奇这n个城市之间究竟有多少种可能的连接方法，于是她向你求助。
方法数可能很大，你只需要输出方法数模1000000007后的结果。

Input

输入共一行，为3个整数n，m，K。

Output

输出1个整数，表示方案数模1000000007后的结果。

Sample Input

【输入样例1】

3 4 1

【输入样例2】

4 3 3

Sample Output

【输出样例1】

3

【输出样例2】

4

【数据规模】

HINT

100%的数据满足1<= n <= 30, 0 <= m <= 30, 1 <= K <= 8.

【题目说明】

两种可能的连接方法不同当且仅当存在一对城市，它们间的道路数在两种方法中不同。
在交通网络中，有可能存在两个城市无法互相到达。

题解

一开始以为是对每个点把后K个点压起来……然后越想越不可行……
后来是把前面的点的奇偶性压起来，枚举每条边加和不加
f[i][j][S][k]表示考虑到第i个点，现在用了j条边，[i-K,i]的点的奇偶性是S，现在考虑的是第i-K + k的点
我们枚举每条边转移和不转移
（其实如果没有偶数边限制的话，这就是个普通的dp……orzzzz）

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define MOD 1000000007
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  10. int f[35][35][(1 << 9) + 2][10];
  11. int n,m,k;
  12. int main() {
  13. #ifdef ivorysi
  14.     freopen("f1.in","r",stdin);
  15. #endif
  16.     scanf("%d%d%d",&n,&m,&k);
  17.     f[2][0][0][0] = 1;
  18.     for(int i = 2 ; i <= n ; ++i) {
  19.     for(int j = 0 ; j <= m ; ++j) {
  20.         for(int s = 0 ; s < (1 << 9) ; ++s) {
  21.         for(int c = 0 ; c < k ; ++c) {
  22.             if(f[i][j][s][c] == 0) continue;
  23.             f[i][j][s][c + 1] += f[i][j][s][c];//这条边不加
  24.             f[i][j][s][c + 1] %= MOD;
  25.             if(j < m && i - k + c >= 1) {
  26.             f[i][j + 1][s ^ (1 << k) ^ (1 << c)][c] += f[i][j][s][c];//这条边加
  27.             f[i][j + 1][s ^ (1 << k) ^ (1 << c)][c] %= MOD;
  28.             } 
  29.         }
  30.         if((s & 1) == 0) f[i + 1][j][s >> 1][0] = f[i][j][s][k];//这个点考虑完了，转移到下一个点，但是必须要第i - K个点奇偶性合法
  31.         }
  32.     }
  33.     }
  34.     printf("%d\n",f[n + 1][m][0][0]);
  35. }

BZOJ 4067: [Ctsc2015]gender

Time Limit: 50 Sec Memory Limit: 20480 MB
Submit: 208 Solved: 70
[Submit][Status][Discuss]

Description

21世纪是生命科学的世纪。人类投入了大量人力物力研究生命科学，旨在对各类生物的生存机理产生更加深入的理解，
以更好地了解人类自身，提高生活质量。Q国政府首先在绵羊中开展了性别改造研究，希望通过基因重组改变性别的方式
增强整个绵羊种群的生存能力。若此计划能够顺利研究成功，人类将掌握随意改变动物性别的黑科技，这将是生命科学
研究史上一个重要的里程碑。
Q国政府从绵羊群中挑出M只绵羊作为实验样本，这M只绵羊中存在K条长度为N的单一性别的血缘链。所谓“血缘链”
是指的一条由父（母）子（女）关系组成的链，比如爷爷-爸爸-儿子就是一条血缘链。“单一性别”的意思是每条血缘链中所有个体的性别均一致，同为雄性或同为雌性。血缘链长度指的是一条血缘链中个体的数量，比如爷爷-爸爸-儿子是一条长度为3的血缘链。这K条血缘链并不相交。
注意并不是每只绵羊都必须属于一条血缘链，有些绵羊可能不属于任何血缘链，因此N*K<=M。除去血缘链外，同辈绵羊还会有“繁衍关系”的存在。两只异性绵羊如果曾经繁殖过后代，那么它们之间就会产生“繁衍关系”。注意繁衍关系只会出现在同辈异性绵羊个体之间，这里“同辈”表示两只绵羊的辈份相同，即绵羊只会与它的兄弟姐妹辈产生“繁衍关系”，而不会与父母或子女或其他更远的辈份之间产生“繁衍关系”。
对绵羊进行性别修改需要花费巨大的实验开销，修改绵羊i的性别需要花费ci的修改代价。除此以外，修改绵羊性别还会对繁衍关系的稳定度产生影响：每对繁衍关系j有初始稳定度bj和衰减系数dj，当所有的性别修改操作完成后，若双方性别均未改变，则此关系稳定度sj=bj，若双方性别互换，则稳定度sj=floor(bjdj)，其他情况下稳定度sj=0。
给定每只绵羊的性别、性别修改代价、所有血缘链关系很繁衍关系，Q国政府希望你来设计一套性别搞糟方案，使总收益最大。
收益计算方式如下：
其中A为改造后血缘链相邻两者为异性的情况数量，S为改造后繁衍关系稳定度之和，即S=∑jsj，C为修改绵羊性别带来的代价之和，即C=∑ici。

Input

第一行包含四个非负整数N,K,M,P，分别为血缘链的长度，血缘链的数量，实验样本中的总绵羊数和繁衍关系的数量。
第二行为一个M个字符的字符串，每个字符为'M'或'F'，描述了这M只绵羊的初始性别。'M'表示雄性，'F'表示雌性。
第三行M个正整数ci，表示修改每只绵羊性别的代价。
下面K行每行N个整数，分别描述这K个血缘链中绵羊编号（所有绵羊用1到M的整数编号），保证每条链中的绵羊均为同性，
且链互补交叠。
下面P行每行三个整数x,y,b和一个实属d，表示绵羊x与绵羊y存在繁衍关系，且初始关系稳定度为b，衰减系数为d。
保证x与y的初始性别不同，x和y为同辈，同一条关系只会在数据中描述一次。

Output

仅包含一行一个整数，表示改造计划的最大收益。

Sample Input

3 2 6 2
MMMFFF
10000 200 10 10000 200 10
1 2 3
4 5 6
2 5 20 0.1
3 6 20 0.9

Sample Output

360

HINT

样例解释1：

改性别为MMFFFM。收益为。
A=2是因为血缘链1-2-3中2与3性别的不同，血缘链4-5-6中5与6的性别不同。

数据范围

对于10%的数据，满足M<=20；
对于10%的数据，满足dj=0；
对于10%的数据，满足dj=0.5；
上述三类数据两两没有交集。
对于100%的数据，N<=50，K<=4，M<=1000，P<=10000，0.0<=dj<=1.0，bj和ci均不大于10000，dj的小数位数不超过6。

题解

我们……想一下怎么转移，首先我们发现那个带log的式子是拆不掉的，但是A很小，我们考虑枚举
然后考虑A确定的时候，某一层的2^K选择方式到底是多少，然后dp到A的最大是多少
就是，我们虽然不确定A能不能达到，但是！我们还是枚举了，并且用dp尝试这个值是否会合法存在，如果不会合法存在，大概就是个负无穷，不影响答案
A确定的时候，第z层的某个状态S的大小的答案应该是多少呢？
似乎还要枚举一遍10000个繁衍关系能不能选，就变成了2^玄学？
然而我们用网络流！！！去求一个转移值！
考虑最小割，如果c1 >= c2 - val u - val v
那么就是c1 + val u + val v >= c2
我们会希望割值是c2
如果反过来会希望割值是c1 + val u + val v
那么建图就可以把每个关系拆出两个点来，A和B，源点到A连一条值为c2的边，A到u和v连正无穷的边，u和v连B一个正无穷的边，B和汇点连一条容量为c1的边，然后每个点如果状态没被确定，和汇点连一条容量为花费的边，如果点状态确定是不被修改，证明c2必然不选，它到汇点连一条正无穷的边，如果点状态确定是被修改，证明c1必然不选，源点到它连一条容量为正无穷的边
sum设成c1 和 c2的总和，然后减去最小割
然后就用dp啦
f[i][j][S]表示第i层，有了j个不同的，最后一层的状态是S
然后用网络流求来的东西转移

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. #define MOD 1000000007
  7. #define MAXM 10005
  8. //#define ivorysi
  9. using namespace std;
  10. typedef long long ll;
  11. struct data {
  12.     int to,next;
  13.     ll val;
  14. }edge[2000005];
  15. int head[30005],sumedge,source,sink;
  16. int dis[30005],gap[30005],n,k,m,p;
  17. void add(int u,int v,ll c) {
  18.     edge[++sumedge].to = v;
  19.     edge[sumedge].next = head[u];
  20.     head[u] = sumedge;
  21.     edge[sumedge].val = c;
  22. }
  23. void addtwo(int u,int v,ll c) {
  24.     add(u,v,c);
  25.     add(v,u,0);
  26. }
  27. ll sap(int u,ll aug) {
  28.     if(u == sink) return aug;
  29.     int dmin = sink - 1;
  30.     ll flow = 0;
  31.     for(int i = head[u] ; i ; i = edge[i].next) {
  32.     int v = edge[i].to;
  33.     if(edge[i].val > 0) {
  34.         if(dis[v] + 1 == dis[u]) {
  35.         int t = sap(v,min(aug - flow,edge[i].val));
  36.         edge[i].val -= t;
  37.         edge[i ^ 1].val += t;
  38.         flow += t;
  39.         if(flow == aug) return flow;
  40.         if(dis[source] >= sink) return flow;
  41.         }
  42.         dmin = min(dis[v],dmin);
  43.     }
  44.     }
  45.     if(!flow) {
  46.     --gap[dis[u]];
  47.     if(gap[dis[u]] == 0) dis[source] = sink;
  48.     dis[u] = dmin + 1;
  49.     ++gap[dis[u]];
  50.     }
  51.     return flow;
  52. }
  53. struct node {
  54.     int u,v,s;
  55.     double d;
  56. }fy[100005];
  57. char str[MAXM];
  58. int id[MAXM],bei[MAXM],ln[205],fa[MAXM];
  59. ll cost[MAXM],g[55][24],f[55][205][24],ans;
  60. int getfa(int x) {
  61.     return x == fa[x] ? x : fa[x] = getfa(fa[x]);
  62. }
  63. void solve(int A,int z,int state) {
  64.     memset(head,0,sizeof(head));
  65.     memset(dis,0,sizeof(dis));
  66.     memset(gap,0,sizeof(gap));
  67.     sumedge = 1;
  68.     source = 1 ; sink = m + p * 2 + 2;
  69.     ll sum = 0;
  70.     for(int i = 1 ; i <= m ; ++i) {
  71.     if(bei[i] == z) {
  72.         if(id[i]) {
  73.         if(state & (1 << id[i] - 1)) { sum -= cost[i];addtwo(source,i + 1,0x7fffffff);}
  74.         else addtwo(i + 1,sink,0x7fffffff);
  75.         }
  76.         else addtwo(i + 1,sink,cost[i]);
  77.     } 
  78.     }
  79.     int T = m + 1;
  80.     for(int i = 1 ; i <= p ; ++i) {
  81.     if(bei[fy[i].u] == z && bei[fy[i].v] == z) {
  82.         ll c1 = 1LL * A * fy[i].s , c2 = 1LL * A * floor(fy[i].s * fy[i].d);
  83.         ++T;
  84.         addtwo(source,T,c2);
  85.         addtwo(T,fy[i].u + 1,0x7fffffff);
  86.         addtwo(T,fy[i].v + 1,0x7fffffff);
  87.         ++T;
  88.         addtwo(T,sink,c1);
  89.         addtwo(fy[i].u + 1,T,0x7fffffff);
  90.         addtwo(fy[i].v + 1,T,0x7fffffff);
  91.         sum += c1 + c2;
  92.     }
  93.     }
  94.     while(dis[source] < sink) sum -= sap(source,1000000000000LL);
  95.     g[z][state] = sum;
  96. }
  97. int calc(int x,int y) {
  98.     int res = 0;
  99.     for(int h = 1 ; h < (1 << k) ; h <<= 1) {
  100.     if((x & h) != (y & h)) ++res;
  101.     }
  102.     return res;
  103. }
  104. void dp(int l) {
  105.     for(int i = 1 ; i <= n ; ++i) {
  106.     for(int j = 0 ; j <= l ; ++j) {
  107.         for(int h = 0 ; h < (1 << k) ; ++h) {
  108.         f[i][j][h] = -100000000000000LL;
  109.         }
  110.     }
  111.     }
  112.     for(int h = 0 ; h < (1 << k) ; ++h) f[1][0][h] = max(f[1][0][h],g[1][h]);
  113.     for(int i = 1 ; i < n ; ++i) {
  114.     for(int j = 0 ; j <= l ; ++j) {
  115.         for(int y = 0 ; y < (1 << k) ; ++y) {
  116.         if(f[i][j][y] == -100000000000000LL) continue;
  117.         for(int x = 0 ; x < (1 << k) ; ++x) {
  118.             int t = calc(x,y) + j;
  119.             f[i + 1][t][x] = max(f[i + 1][t][x] , f[i][j][y] + g[i + 1][x]);
  120.         }
  121.         }
  122.     }
  123.     }
  124. }
  125. int main() {
  126. #ifdef ivorysi
  127.     freopen("f1.in","r",stdin);
  128. #endif
  129.     scanf("%d%d%d%d",&n,&k,&m,&p);
  130.     scanf("%s",str + 1);
  131.     for(int i = 1 ; i <= m ; ++i) scanf("%lld",&cost[i]);
  132.     for(int i = 1 ; i <= k ; ++i) {
  133.     for(int j = 1 ; j <= n ; ++j) {
  134.         int x;
  135.         scanf("%d",&x);
  136.         bei[x] = j;
  137.         id[x] = i;
  138.     }
  139.     }
  140.     for(int i = 1 ; i <= m ; ++i) fa[i] = i;
  141.     for(int i = 1 ; i <= p ; ++i) {
  142.     scanf("%d%d%d%lf",&fy[i].u,&fy[i].v,&fy[i].s,&fy[i].d);
  143.     fa[getfa(fy[i].u)] = getfa(fy[i].v); 
  144.     }
  145.     for(int i = 1 ; i <= m ; ++i) if(bei[i]) bei[getfa(i)] = bei[i];//这个需要用并查集，之后一次性更新，因为……我们可能有两只羊有繁衍关系但是他们不在任何一条链内
  146.     for(int i = 1 ; i <= m ; ++i) bei[i] = bei[getfa(i)];
  147.     for(int i = 1 ; i <= m ; ++i) if(!bei[i]) bei[i] = 1;
  148.     for(int i = 1 ; i <= k * n ; ++i) {
  149.     ln[i] = (int)(10*log(i + 1));
  150.     if(ln[i] != ln[i - 1]) {
  151.         for(int j = 1; j <= n ; ++j) {
  152.         for(int h = 0 ; h < (1<<k) ; ++h) {
  153.             solve(ln[i],j,h);
  154.         }
  155.         }
  156.         dp(i);
  157.     }
  158.     for(int h = 0 ; h < (1 << k) ; ++h) ans = max(ans,f[n][i][h]);
  159.     }
  160.     printf("%lld\n",ans);
  161. }

BZOJ 1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 8947 Solved: 4053
[Submit][Status][Discuss]

Description

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？

Input

包含两个整数，A B。

Output

一个整数

Sample Input

【输入样例一】

1 10

【输入样例二】

25 50

Sample Output

【输出样例一】

9

【输出样例二】

20

HINT

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

题解

f[i][j][2]枚举到第i位，i位开头数字是j，1/0表示是否大于这个数

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. #define MOD 1000000007
  7. #define MAXM 10005
  8. //#define ivorysi
  9. using namespace std;
  10. typedef long long ll;
  11. int A,B,c[11][11];
  12. int f[11][11][2],a[15],tot;
  13. int DP(int x) {
  14.     memset(f,0,sizeof(f));
  15.     tot = 0;
  16.     while(x) a[++tot] = x % 10 , x /= 10;
  17.     if(tot == 0) a[++tot] = 0;
  18.     for(int i = 0 ; i <= 9 ; ++i) {
  19.     if(i <= a[1]) f[1][i][0] = 1;
  20.     else f[1][i][1] = 1;
  21.     }
  22.     for(int i = 2 ; i <= tot ; ++i) {
  23.     for(int j = 0 ; j <= 9 ; ++j) {
  24.         for(int k = 0 ; k <= 9 ; ++k) {
  25.         if(c[j][k] >= 2) {
  26.             if(k < a[i]) {
  27.             f[i][k][0] += f[i - 1][j][0] + f[i - 1][j][1];
  28.             }
  29.             else if(k == a[i]) {
  30.             f[i][k][0] += f[i - 1][j][0];
  31.             f[i][k][1] += f[i - 1][j][1];
  32.             }
  33.             else {
  34.             f[i][k][1] += f[i - 1][j][0] + f[i - 1][j][1];
  35.             }
  36.         }
  37.         }
  38.     }
  39.     }
  40.     int res = 0;
  41.     for(int i = 1 ; i <= a[tot] ; ++i) {
  42.     if(i < a[tot]) res += f[tot][i][0] + f[tot][i][1];
  43.     else if(i == a[tot])res += f[tot][i][0];
  44.     }
  45.     for(int i = tot - 1 ; i >= 1 ; --i) {
  46.     for(int j = 1 ; j <= 9 ; ++j) {
  47.         res += f[i][j][0] + f[i][j][1];
  48.     }
  49.     }
  50.     return res;
  51. }
  52. int main() {
  53. #ifdef ivorysi
  54.     freopen("f1.in","r",stdin);
  55. #endif
  56.     for(int i = 0 ; i <= 9 ; ++i) {
  57.     for(int j = i ; j <= 9 ; ++j) {
  58.         c[i][j] = c[j][i] = j - i;
  59.     }
  60.     }
  61.     scanf("%d%d",&A,&B);
  62.     printf("%d\n",DP(B) - DP(A - 1));
  63. }

HDU 2089 不要62

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 49215 Accepted Submission(s): 18574

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m（0< n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100
0 0

Sample Output

80

　题解

如果前一位是2，这一位是6就不转移
如果前一位或这一位是4，就不转移

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. #define MOD 1000000007
  7. #define MAXM 10005
  8. //#define ivorysi
  9. using namespace std;
  10. typedef long long ll;
  11. int A,B,c[11][11];
  12. int f[11][11][2],a[15],tot;
  13. int DP(int x) {
  14.     if(x == 0) return 0;
  15.     memset(f,0,sizeof(f));
  16.     tot = 0;
  17.     while(x) a[++tot] = x % 10 , x /= 10;
  18.     for(int i = 0 ; i <= 9 ; ++i) {
  19.     if(i <= a[1]) f[1][i][0] = 1;
  20.     else f[1][i][1] = 1;
  21.     }
  22.     f[1][4][0] = f[1][4][1] = 0;
  23.     for(int i = 2 ; i <= tot ; ++i) {
  24.     for(int j = 0 ; j <= 9 ; ++j) {
  25.         for(int k = 0 ; k <= 9 ; ++k) {
  26.         if(k == 6 && j == 2) continue;
  27.         if(k == 4 || j == 4) continue;
  28.         if(k < a[i]) {
  29.             f[i][k][0] += f[i - 1][j][1] + f[i - 1][j][0];
  30.         }
  31.         else if(k == a[i]) {
  32.             f[i][k][0] += f[i - 1][j][0];
  33.             f[i][k][1] += f[i - 1][j][1];
  34.         }
  35.         else {
  36.             f[i][k][1] += f[i - 1][j][0] + f[i - 1][j][1];
  37.         }
  38.         }
  39.     }
  40.     }
  41.     int res = 0;
  42.     for(int i = 1 ; i <= a[tot] ; ++i) {
  43.     if(i < a[tot]) res += f[tot][i][0] + f[tot][i][1];
  44.     else if(i == a[tot])res += f[tot][i][0];
  45.     }
  46.     for(int i = tot - 1 ; i >= 1 ; --i) {
  47.     for(int j = 1 ; j <= 9 ; ++j) {
  48.         res += f[i][j][0] + f[i][j][1];
  49.     }
  50.     }
  51.     return res;
  52. }
  53. int main() {
  54. #ifdef ivorysi
  55.     freopen("f1.in","r",stdin);
  56. #endif
  58.     while(scanf("%d%d",&A,&B)) {
  59.     if(A + B == 0) break;
  60.     printf("%d\n",DP(B) - DP(A - 1));
  61.     }
  62. }

HDU 3652 B-number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7463 Accepted Submission(s): 4376

Problem Description

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.

Input

Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

Output

Print each answer in a single line.

Sample Input

13
100
200
1000

Sample Output

1
1
2
2

题解

我这个代码写的是真的不清真
f[i][j][h][2][2]
表示第i位，开头是j，%13后的值，是否有13,是否大于目标值

如果能凑成一个13第4位直接是1，然后全部更新
如果不能凑成，第四位看它后面的数能不能凑成13，能凑成就是1，不能凑成就是0

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. int B;
  10. ll f[11][11][14][2][2];
  11. int a[15],tot,base[11];
  12. int DP(int x) {
  13.     if(x == 0) return 0;
  14.     memset(f,0,sizeof(f));
  15.     tot = 0;
  16.     while(x) a[++tot] = x % 10 , x /= 10;
  17.     for(int i = 0 ; i <= 9 ; ++i) {
  18.     if(i <= a[1]) f[1][i][i][0][0] = 1;
  19.     else f[1][i][i][0][1] = 1;
  20.     }
  21.     for(int i = 2 ; i <= tot ; ++i) {
  22.     for(int j = 0 ; j <= 9 ; ++j) {
  23.         for(int k = 0 ; k <= 9 ; ++k) {
  24.         for(int h = 0 ; h < 13 ; ++h) {
  25.             int t = 0;
  26.             if(j == 3 && k == 1) t = 1;
  27.             if(k < a[i]) {
  28.             if(t) {
  29.                 f[i][k][(h + k * base[i - 1]) % 13][t][0] += f[i - 1][j][h][1][0] + f[i - 1][j][h][1][1] +
  30.                 f[i - 1][j][h][0][0] + f[i - 1][j][h][0][1];
  31.             }
  32.             else {
  33.                  f[i][k][(h + k * base[i - 1]) % 13][0][0] += f[i - 1][j][h][0][0] + f[i - 1][j][h][0][1];
  34.                  f[i][k][(h + k * base[i - 1]) % 13][1][0] += f[i - 1][j][h][1][0] + f[i - 1][j][h][1][1];
  35.             }
  36.             }
  37.             else if(k == a[i]) {
  38.             if(t) {
  39.                 f[i][k][(h + k * base[i - 1]) % 13][t][0] += f[i - 1][j][h][1][0] + f[i - 1][j][h][0][0];
  40.                 f[i][k][(h + k * base[i - 1]) % 13][t][1] += f[i - 1][j][h][1][1] + f[i - 1][j][h][0][1];
  41.             }
  42.             else {
  43.                 f[i][k][(h + k * base[i - 1]) % 13][0][0] += f[i - 1][j][h][0][0];
  44.                 f[i][k][(h + k * base[i - 1]) % 13][1][0] += f[i - 1][j][h][1][0];
  45.                 f[i][k][(h + k * base[i - 1]) % 13][0][1] += f[i - 1][j][h][0][1];
  46.                 f[i][k][(h + k * base[i - 1]) % 13][1][1] += f[i - 1][j][h][1][1];
  47.             }
  48.             }
  49.             else {
  50.             if(t) {
  51.                 f[i][k][(h + k * base[i - 1]) % 13][t][1] += f[i - 1][j][h][1][0] + f[i - 1][j][h][1][1] +
  52.                 f[i - 1][j][h][0][0] + f[i - 1][j][h][0][1];
  53.             }
  54.             else {
  55.                 f[i][k][(h + k * base[i - 1]) % 13][0][1] += f[i - 1][j][h][0][0] + f[i - 1][j][h][0][1];
  56.                 f[i][k][(h + k * base[i - 1]) % 13][1][1] += f[i - 1][j][h][1][0] + f[i - 1][j][h][1][1];
  57.             }
  58.             }
  59.         }
  60.         }
  61.     }
  62.     }
  63.     int res = 0;
  64.     for(int i = 1; i <= a[tot] ; ++i) {
  65.     if(i < a[tot]) res += f[tot][i][0][1][0] + f[tot][i][0][1][1];
  66.     else if(i == a[tot]) res += f[tot][i][0][1][0];
  67.     }
  68.     for(int i = tot - 1 ; i >= 1 ; --i) {
  69.     for(int j = 1 ; j <= 9 ; ++j) {
  70.         res += f[i][j][0][1][0] + f[i][j][0][1][1];
  71.     }
  72.     }
  73.     return res;
  74. }
  75. int main() {
  76. #ifdef ivorysi
  77.     freopen("f1.in","r",stdin);
  78. #endif
  79.     base[0] = 1;
  80.     for(int i = 1 ; i <= 10 ; ++i) {
  81.     base[i] = base[i - 1] * 10 % 13;
  82.     }
  83.     while(scanf("%d",&B) != EOF) {
  84.     printf("%d\n",DP(B));
  85.     }
  86. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注