USACO DEC09 Cow Toll Paths

这题的难点在于如何处理点的权值对最小费用路径的影响。本人也是在看了题解后才弄明白的。

需要用到两个二维数组:cost,dist
dist[i][j]表示i到j的传统意义上的距离
cost[i][j]表示i到j的费用

那么就有cost[i][j] = dist[i][j] + 路径上点的C最大值。

然而，我们并不能在求出最短路前预先知道路径上那个点的C最大啊。既然这样不行，那么我们就指定一个C最大的点吧。

因此，把所有点按照C从小到大排序。然后，对Floyd进行如下修改：让最外层循环的点k的C保持递增，那么对于内层的i和j，max(C[i],C[j],C[k])就是当前路径上C的最大值了。不断更新dist和cost数组。最后读入请求输出对应cost中的值即可。

这个算法用到了Floyd的一个很有趣性质，本人将在以后的文章中进行更深入的探究。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 260
#define INF 1000000000

long dist[MAXN][MAXN];
long cost[MAXN][MAXN];
long c[MAXN],v[MAXN];
int N,M,K;

void init()
{
   int i,j,a,b;
   long t;
   scanf("%d%d%d",&N,&M,&K);
   for(i = 1;i <= N;i ++)
       for(j = 1;j <= N;j ++)
           dist[i][j] = cost[i][j] = INF;
   for(i = 1;i <= N;i ++)
   {
       scanf("%ld",&c[i]);
       v[i] = i;
   }
   for(i = 1;i <= M;i ++)
   {
       scanf("%d%d%ld",&a,&b,&t);
       if(dist[a][b] > t)
           dist[a][b] = dist[b][a] = t;
   }
   for(i = 1;i <= N;i ++)
       for(j = i + 1;j <= N;j ++)
           if(c[v[i]] > c[v[j]])
           {
               t = v[i];v[i] = v[j];v[j] = t;
           }
}

inline long getmax(long a,long b)
{
   if(a > b)    return a;
   return b;
}

void floyd()
{
   int i,j,t,k;
   for(t = 1;t <= N;t ++)
   {
       k = v[t];
       for(i = 1;i <= N;i ++)
           for(j = 1;j <= N;j ++)
           {
               if(dist[i][j] > dist[i][k] + dist[k][j])
                   dist[i][j] = dist[i][k] + dist[k][j];
               if(cost[i][j] > dist[i][j] + getmax(getmax(c[i],c[j]),c[k]))
                   cost[i][j] = dist[i][j] + getmax(getmax(c[i],c[j]),c[k]);
           }
   }
}

void output()
{
   int i,a,b;
   for(i = 1;i <= K;i ++)
   {
       scanf("%d%d",&a,&b);
       printf("%ld\n",cost[a][b]);
   }
}

int main()
{
   freopen("toll.in","r",stdin);
   freopen("toll.out","w",stdout);
   init();
   floyd();
   output();
   fclose(stdout);
   return 0;
}

安排警卫题解

题目大意：有一个由N个节点构成的树，在每个节点安排警卫的花费都不同，只有在某个节点布置警卫，或者在其某个相邻节点布置警卫，才可以保证这个节点安全。求：要让所有节点都安全，最少的花费是多少。

容易看出问题的最优子结构性质，因此考虑树形动态规划。那么，要如何表示状态呢？本人用f[x][0]表示在x节点不放置警卫，使以x为根的子树安全的最小花费；f[x][1]表示在x放置警卫，使以x为根的子树安全的最小花费。不过，这个状态表示不能包括下面这个情形：
[1](10)------[2](20)------[3](30)------[4](5)
方括号内是节点编号，圆括号内是安排警卫的费用， 此时的最优解是15,而本人的解是25.

因此，增加一个状态，用f[x][2]表示不再x安排警卫，在x的父亲节点安排。

由于转移方程要考虑多种情况，较为复杂，读者请直接看代码。

广场铺砖问题——状态压缩动态规划

题目大意：有一个长H，宽W的广场，要铺满2x1规格的砖块，不允许砖块重叠，求一共有多少种方案？（H，W均不超过11）

题目的数据范围相当小，不过还没有小到可以用DFS解决的规模（DFS每次只能把方案数增加1,而W=10,H=11的方案数为已经超过10^11了）。

注意到题目的砖块只有两种摆放方式：横着或者竖着。加之广场边长小于11,因此考虑用状态压缩动态规划（不熟悉这个名词的读者可以参考这篇文章）。用一个整数的每一位对应一个横排每个位置是否有砖块。
那么，转移方程就是：F[i][S] = Sigma{F[i-1][S']} (S'可以转移到S)
边界是：F[1][0] = 1

现在要做的就是找出各个状态之间的转移关系。这时DFS就派上用场了，我们只需考虑两行，枚举第一行的状态i，根据i搜索得到第二行能达到的状态j，把adj[i][j]赋值为1.具体实现请看后面的程序。

获得矩阵adj后，就可以用三个for逐行求出F[i][S]的方案了，最后输出F[H+1][0]（或者F[H][(1 << W) - 1]）.

此外，由于砖块的面积是2，如果广场面积是奇数，显然是无解的，可以直接输出0.

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

long long f[13][2050];
_Bool adj[2050][2050];    //所有可能的转移
int W,H;

void dfs(int from,int step,int to)
{
   if(step == W)
   {
       adj[from][to] = 1;
       return;
   }
   if(((1 << step) & from) != 0)    //已经放过，考察下一个
       dfs(from,step + 1,to);
   else
   {
       if((step <= W - 2) && ((1 << (step + 1)) & from) == 0)    //两块都是空的，可以横放
               dfs(from,step + 2,to);
       dfs(from,step + 1,to | (1 << step));   //竖着放
   }
}

int main()
{
   freopen("floor.in","r",stdin);
   freopen("floor.out","w",stdout);
   scanf("%d%d",&W,&H);
   if((W * H) % 2 == 1)    //无解情况
   {
       printf("0\n");
       fclose(stdout);
       exit(0);
   }
   int max = 1 << W;
   int i,j,k;
   for(i = 0;i < max;i ++)    //DFS构建矩阵
       dfs(i,0,0);
   f[0][0] = 1;
   for(i = 0;i < H;i ++)
       for(j = 0;j < max;j ++)
           for(k = 0;k < max;k ++)
               if(adj[j][k])    f[i + 1][k] += f[i][j];
   printf("%I64d\n",f[H][0]);
   fclose(stdout);
   return 0;
}

压缩字符串题解

输入一个仅由大写字母组成的字符串（长度不超过100），可以用如下规则压缩：

1. 如果遇到连续的重复字串，可以只保留一个，在其两边用"n(",")"标记，n表示重复的次数。
2. 括号的使用可以嵌套。

使用以上规则，尽可能压缩字符串（即使压缩后的串尽量短），输出压缩结果。

比如：
AAAAAAAAA           ->    9(A)
AAAAAABBBBBB    ->     6(A)6(B)
AA                          ->     AA
ICICICICICI              ->     4(IC)I
AAAAABBBBBAAAAABBBBB   ->     2(5(A)5(B))

这是一题的最优子结构性质非常明显，是典型的区间动态规划题。
用f[i][j]表示i~j这个字符串最小的长度。
显然，
f[i][j] = min{j - i + 1,f[i][k] + f[k + 1][j],compress(f[i][j])}
i<=k由于需要输出字符，因此增加一个s[i][j][MAXLEN]记录str[i]~str[j]压缩后的情况。

s[0][len - 1]就是最终结果。

需要注意，动态规划的特性决定了它会对所有可能的情况作出转移并选择最优的。因此在写动规方程的时候要注意避免没有必要的转移（或者重复的转移）。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXLEN 101 char str[MAXLEN]; int len; char s[MAXLEN][MAXLEN][MAXLEN] = {}; int f[MAXLEN][MAXLEN]; int numlen(int x) {     if(x >= 100)   return 3;     if(x >= 10)    return 2;     return 1; } void output() {     int i;     for(i = 0;i < f[0][len - 1];i ++)         printf("%c",s[0][len - 1][i]);     printf("\n"); } int find(int b,int l,int e) {     int i,r = 1;     for(i = b + l;i <= e - l + 1;i += l)     {         if(strncmp(str + b,str + i,l) != 0)   return 0;         r ++;     }     return r; } void solve() {     int l,j,k,i,seg;     int r,newlen;     char tmp[MAXLEN];     for(i = 0;i < len;i ++)         for(j = i;j < len;j ++)         {             f[i][j] = j - i + 1;             memcpy(s[i][j],str + i,j - i + 1);         }     for(l = 2;l <= len;l ++)         for(i = 0;i < len;i ++)         {             j = l + i - 1;             if(j >= len)   break;             for(seg = 1;seg < l;seg ++)                 if(l % seg == 0)                 {                     r = find(i,seg,j);                     if(r == 0)    continue;                     newlen = numlen(r) + 2 + f[i][i + seg - 1];   //寻找重复串                     if(newlen < f[i][j])                     {                         f[i][j] = newlen;                         sprintf(s[i][j],"%d(",r);                         strcat(s[i][j],s[i][i + seg - 1]);                         strcat(s[i][j],")");                     }                 }             for(k = i;k < j;k ++)             {                 if(f[i][k] + f[k + 1][j] < f[i][j])                 {                     f[i][j] = f[i][k] + f[k + 1][j];                     strcpy(s[i][j],s[i][k]);                     strcat(s[i][j],s[k+1][j]);                 }             }             //fprintf(stderr,"(%d,%d):%s\n",i,j,s[i][j]);         } } int main() {     freopen("cipher.out","w",stdout);     freopen("cipher.in","r",stdin);     scanf("%s\n",str);     len = strlen(str);     solve();     output();     fclose(stdout);     return 0; }

甲虫喝水题解

题目来源：NOI导刊，NOIP模拟试题八
题目描述：有一只甲虫位于x轴的原点，在任何时刻，它可以选择左右两个方向移动，并且移动一个单位长度需要耗时1s。x轴上的N个点上有露珠。起始时刻，每个露珠的含水量都是正整数M，每经过1s，每个露珠的含水量减少1单位。当甲虫遇到露珠时，它可以在瞬间喝光露珠的水。
输入N,M和每个露珠的位置（露珠位置为整数），输出甲虫能喝到的最多的水量。

比如：N=3 M=15 露珠位置分别为6、-3、1时，甲虫可以依次喝1、-3、6处的露水，获得最大水量25

可以明确一下几点：

1. 甲虫只会在有露珠的位置掉转方向。
2. 一旦遇到露珠，甲虫一定会喝掉。
3. 每个时刻所有未喝掉的露珠水量都会均匀减少。

故甲虫喝掉的水一定是一个连续的区间。

因此，这个题目就是一道区间动规题。
首先，先对露珠的位置排序。
用fi[i][j][k]表示一共要吃掉k颗露水，目前吃光了i到j之间的露水并停留在i端的情况。fj[i][j][k]表示停留在j端的情况。增加k这一维，预先扣除剩余(k-i+j)颗露水的减少量，就可以解决露珠水量减少的问题。

具体的转移方程可以参考下面的代码。数组中k这一维可以压缩掉。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 303

long x[MAXN];
long N,M;
long ans;
long fi[MAXN][MAXN];
long fj[MAXN][MAXN];

int cmp(const void *a,const void *b)
{
   if(*(long *)a > *(long *)b)    return 1;
   return -1;
}

void init()
{
   scanf("%ld%ld",&N,&M);
   long i;
   for(i = 0;i < N;i ++)
       scanf("%ld",&x[i]);
   qsort(x,N,sizeof(long),cmp);
}

inline long getmax(long a,long b)
{
   if(a > b)    return a;
   return b;
}

void solve()
{
   ans = 0;
   int i,j,k,l;
   for(k = 1;k <= N;k ++)
   {
       for(i = 0;i < N;i ++)
       {
           fi[i][i] = fj[i][i] = M - labs(x[i]) * k;
           ans = getmax(ans,fi[i][i]);
       }
       for(l = 2;l <= k;l ++)
           for(i = 0;i <= N - l;i ++)
           {
               j = i + l - 1;
               fi[i][j] = M + getmax(fi[i + 1][j] - (x[i + 1] - x[i]) * (k - j + i),fj[i + 1][j] - (x[j] - x[i]) * (k - j + i));
               fj[i][j] = M + getmax(fi[i][j - 1] - (x[j] - x[i]) * (k - j + i),fj[i][j - 1] - (x[j] - x[j - 1]) * (k - j + i));
               ans = getmax(fi[i][j],ans);
               ans = getmax(fj[i][j],ans);
           }
   }
   printf("%ld\n",ans);
}

int main()
{
   freopen("beetle.in","r",stdin);
   freopen("beetle.out","w",stdout);
   init();
   solve();
   return 0;
}

一个奇怪的取数游戏

这是NOI导刊上的一道题目，题目是这么说的：

输入N个整数（它们的范围在-1000~+1000），它们顺次围成一个环。
在这N个数中取出M个数，条件是任意两个取出的数不能相邻，求它们的和的最大值。
如果不能按要求取出M个数，则输出Error!
N的范围是[10,200000]，M一定小于N。

显然，当M > N div 2时，就不能取出M个数了，因此直接退出。

容易想到一个动态规划的解法：
用f[i][j][0]表示不取第i个数，前i个数一共取出了j个数获得的和的最大值；
用f[i][j][1]表示取第i个数，前i个数一共取出了j个数获得的和的最大值。

显然
f[i][j][0] = max{f[i - 1][j][1],f[i - 1][j][0]}
f[i][j][1] = f[i - 1][j - 1][0]
稍微处理下环和边界情况就OK了。

不过呢，这个动态规划的时间复杂度是N^2级别的，对于200000的N是显然行不通的。

==================================================

导刊上给出了一个诡异的解法，用最大堆和双向链表。
首先，用双向链表记录每个位置前后的数的位置，构成一个环形链表。
与此同时，把所有数的编号加入最大堆。
然后，进行M次如下操作：

x = heap[0]
ans += value[x]
value[x] = value[left[x]] + value[right[x]] - value[x]
维护堆
把left[x]和right[x]从堆和双向链表中删去，并维护堆。

最后输出ans

其中value[x] = value[left[x]] + value[right[x]] - value[x]这句话是最关键的，请注意里面的减号，这说明如果某个值被加到了ans里面，在后面的操作中它还有可能被再次减去。就像用Ford-Fulkerson求最大流一样，某些边的流量反而会减小，但是S到T的流量是增加的。

如果按照这个算法，这道题完全可以转化成费用流解，关于如何转化本人还要思考下。

在编写这个程序的时候还有一个小插曲，起初只通过了一半的数据，检查发现每次修改堆中数据后，必须“马上”对堆进行调整，否则会破坏堆的结构。

按照惯例，给出代码：

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 400005
#define pa(x)    (((x) - 1) / 2)
#define lc(x)    ((x) * 2 + 1)
#define rc(x)    ((x) * 2 + 2)

long N,M;
long v[MAXN],heap[MAXN],heapsize,pos[MAXN];
long l[MAXN],r[MAXN];

void moveup(long x)   //x:the index in heap
{
   long tmp;
   while(x > 0 && v[heap[x]] > v[heap[pa(x)]])
   {
       tmp = heap[x];
       heap[x] = heap[pa(x)];
       heap[pa(x)] = tmp;
       tmp = pos[heap[x]];
       pos[heap[x]] = pos[heap[pa(x)]];
       pos[heap[pa(x)]] = tmp;
       x = pa(x);
   }
}

void movedown(long x)
{
   long s,tmp;
   s = x;
   while(1)
   {
       if(lc(x) < heapsize && v[heap[lc(x)]] > v[heap[s]])    s = lc(x);
       if(rc(x) < heapsize && v[heap[rc(x)]] > v[heap[s]])    s = rc(x);
       if(s != x)
       {
           tmp = heap[x];
           heap[x] = heap[s];
           heap[s] = tmp;
           tmp = pos[heap[x]];
           pos[heap[x]] = pos[heap[s]];
           pos[heap[s]] = tmp;
           x = s;
       }
       else break;
   }
}

int main()
{
   freopen("compile.in","r",stdin);
   freopen("compile.out","w",stdout);
   scanf("%ld%ld",&N,&M);
   if(M > N / 2)
   {
       printf("Error!\n");
       fclose(stdout);
       exit(0);
   }
   long i;
   long ans = 0;
   heapsize = 0;
   for(i = 0;i < N;i ++)
   {
       scanf("%ld",&v[i]);
       heap[heapsize] = i;
       pos[i] = heapsize;
       moveup(heapsize);
       heapsize ++;
       l[i] = i - 1;
       r[i] = i + 1;
   }
   l[0] = N - 1;
   r[N - 1] = 0;
   while(M --)
   {
       i = heap[0];
       ans += v[i];
       v[i] = v[l[i]] + v[r[i]] - v[i];
       movedown(0);
       v[l[i]] = -1000000000;    //same effect as removal
       movedown(pos[l[i]]);
       v[r[i]] = -1000000000;
       movedown(pos[r[i]]);
       l[i] = l[l[i]];
       r[i] = r[r[i]];
       l[r[i]] = i;
       r[l[i]] = i;
   }
   printf("%ld\n",ans);
   fclose(stdout);
   return 0;
}

USACO OPEN11 Forgotten Password

Problem 8: Forgotten Password [Damon Doucet, 2011]

As has happened to so many of us, Bessie has forgotten her cowtube
password. She does, however, remember some handy bits of information
about it.

First, she remembers that her password (denoted as variable P) has
length L (1 <= L <= 1,000) roman characters and can be split into
one or more words (not necessarily unique) from a dictionary composed
of NW (1 <= NW <= 1,000) unique words.  A word W_i is defined as a
sequence of 1..20 lowercase letters of the Roman alphabet ('a'..'z').

She also remembers certain letters from her password along with
their positions.

Consider the following example. Bessie knows that her password looks
like "a??l?ban???????" ('?' represents a letter she cannot remember),
and her dictionary has the following words:

apple
cow
farmer
banana
bananas
pies

The two possible passwords for Bessie to have are "applebananapies" and 
"applebananascow".

Given the dictionary, and the letters that Bessie remembers, please
find her password. If more than one password is valid, find the
lexicographically least string that works.

PROBLEM NAME: forgot

INPUT FORMAT:

* Line 1: Two space-separated integers: L and NW

* Line 2: A string of length L: P

* Lines 3..NW+2: Line i+2 contains the ith word in the dictionary: W_i

SAMPLE INPUT (file forgot.in):

15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies

OUTPUT FORMAT:

* Line 1: The lexicographically least password that fits

SAMPLE OUTPUT (file forgot.out):

applebananapies

**********************************************************************

这题有明显的无后效性很明显，使用动态规划解决。类似完全背包，用can[i]记录长度为i的串能否实现，

不断扩展，复杂度为（L*NW*20） 

只是题目要求输出排序后最小的那个，根据最优子结构性质，只要加上一个char str[i][MAXLEN]，记录

长度为i时排序最靠前的那个串即可。

C语言: 高亮代码由发芽网提供

#include
#include
#include

int L,N;
char pass[1005];
char word[1005][25];
int len[1005];
int can[1005];
char str[1005][1005];
char tmp[1005];

void init()
{
   scanf("%d%d\n",&L,&N);
   scanf("%s\n",pass);
   int i;
   for(i = 0;i < N;i ++)
   {
       scanf("%s\n",word[i]);
       len[i] = strlen(word[i]);
   }
}

int match(char *a,char *b)
{
   for(;*a && *b;a ++,b ++)
   {
       if(*b == '?')    continue;
       if(*a != *b)    return 0;
   }
   return 1;
}

void dp()
{
   int i,j;
   can[0] = 1;
   for(i = 0;i <= L;i ++)
       if(can[i])
           for(j = 0;j < N;j ++)
               if(i + len[j] <= L && match(word[j],pass + i))
               {
                   if(can[i + len[j]] == 0)
                   {
                       can[i + len[j]] = 1;
                       memcpy(str[i + len[j]],str[i],i * sizeof(char));
                       memcpy(str[i + len[j]] + i,word[j],len[j] * sizeof(char));
                   }
                   else
                   {
                       strcpy(tmp,str[i]);
                       strcpy(tmp + i,word[j]);
                       if(strcmp(tmp,str[i + len[j]]) < 0)
                           memcpy(str[i + len[j]],tmp,1001 * sizeof(char));
                   }
               }
   puts(str[L]);
}

int main()
{
   freopen("forgot.in","r",stdin);
   freopen("forgot.out","w",stdout);
   init();
   dp();
   return 0;
}

起初本人程序中用得都是strcpy和strcat,在USACO上测试时超时了，换成memcpy就通过了。可见memcpy的效率大大高于strcpy。