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;
}

USACO DEC09 Dizzy Cows

题目的大意就是确定输入的无向边的方向，使得所有无向边加入后依然是一个有向无环图。

思路很直接，先把所有的有向边加入图中，运行一次拓扑排序。如果不能排序，那么原图就有环，输出“-1” 并退出。然后，读入每条无向边(a,b)，若在拓扑序列中a在b前面，则方向为a指向b，否则为b指向a。

由于有多个解，USACO只给了输入数据，没有给输出数据。故本人增加了一个函数check，用于检查程序输出是否正确。

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

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

typedef struct node
{
   long v;
   struct node *next;
}node;

long in[MAXN] = {};  //入度
long Q[MAXN];
long N,M,K;
node space[MAXN];
long empty = 0;
node *first[MAXN];

long pos[MAXN];   //点在拓扑序中的位置

void init()
{
   scanf("%ld%ld%ld\n",&N,&M,&K);
   long i,a,b;
   for(i = 0;i < M;i ++)
   {
       scanf("%ld%ld\n",&a,&b);
       space[empty].v = b;
       space[empty].next = first[a];
       first[a] = space + empty;
       empty ++;
       in[b] ++;
   }
}

void toposort()
{
   node *p;
   long i,head,tail;
   head = tail = 0;
   for(i = 1;i <= N;i ++)
       if(in[i] == 0)    Q[tail ++] = i;
   while(head < tail)
   {
       i = Q[head ++];
       for(p = first[i];p != NULL;p = p->next)
       {
           in[p->v] --;
           if(in[p->v] == 0)
               Q[tail ++] = p->v;
       }
   }
   if(tail < N)
   {
       printf("-1\n");
       exit(0);
   }
   for(i = 0;i < tail;i ++)
       pos[Q[i]] = i;
}

void add(long a,long b)   //用于测试
{
   node *p = malloc(sizeof(node));
   p->v = b;
   p->next = first[a];
   first[a] = p;
}

void check()   //用于测试
{
   node *p;
   int i,head,tail;
   memset(in,0,sizeof(in));
   for(i = 1;i <= N;i ++)
       for(p = first[i];p != NULL;p = p->next)
           in[p->v] ++;
   head = tail = 0;
   for(i = 1;i <= N;i ++)
       if(in[i] == 0)    Q[tail ++] = i;
   while(head < tail)
   {
       i = Q[head ++];
       for(p = first[i];p != NULL;p = p->next)
       {
           in[p->v] --;
           if(in[p->v] == 0)
               Q[tail ++] = p->v;
       }
   }
   if(head == N && tail == N)    fprintf(stderr,"Correct!\n");
   else    fprintf(stderr,"Wrong!\n");
}

void arrange()
{
   long i,a,b;
   for(i = 0;i < K;i ++)
   {
       scanf("%ld%ld",&a,&b);
       if(pos[a] < pos[b])
       {
           printf("%ld %ld\n",a,b);
           add(a,b);
       }
       else
       {
           printf("%ld %ld\n",b,a);
           add(b,a);
       }
   }
}

int main()
{
   freopen("dizzy.in","r",stdin);
   freopen("dizzy.out","w",stdout);
   init();
   toposort();
   arrange();
   check();
   fclose(stdin);
   fclose(stdout);
   return 0;
}

USACO NOV09 Lights

由于灯的上限是35个，因此可以用一个64位整型表示整个状态，二进制1表示灯亮，0表示灯灭。那么，初始状态就是0,目标状态(target)就是(1 << N)-1.
同样，也可以把每个开关改变的灯记录在一个64位整型数组op里，按下开关i后的新状态就等于当前状态xor op[i].

由于xor具有自反性和交换性，因此无需考虑按开关的顺序，每个开关也最多只按一次，否则效果就抵消了。因此很容易写出下面的搜索函数：

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

void dfs(unsigned long long s,int p,int i)
{
   if(success)     return;
   if(p == depth)        //p表示按下开关的数量
   {
       if(s == target)      success = 1;
       return;
   }
   if(i == N)
       return;
   dfs(s,p,i + 1);   //不按开关
   dfs(s ^ op[i],p + 1,i + 1);     //按开关
}

依次增加depth，并运行dfs(0,0,0)，直到success为真，此时的depth就是答案。不过，这个DFS的复杂度是2^N方的，在N=20以下都可以迅速出解，当N=30时就严重超时了。

如何降低复杂度呢？我们要寻找的是一个满足0 xor op[t1] xor op[t2] xor .... xor op[tk] = target的序列，根据xor的交换律和结合律，我们可以把这个序列分成两半求解。本题的关键就在这里。

安排警卫题解

题目大意：有一个由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;
}

包含指定元素的最长上升序列

题目要求：给出一个长度为N整数序列,请求出它的包含第K个元素的最长上升子序列。
很明显，可以求出1~(K-1)中小于v[K]的元素构成的LIS的长度l1,再求出(K+1)~N中大于v[K]的元素构成的LIS的长度l2,l1+l2+1即为包含第K个元素的LIS的长度。

求解LIS的nlogn算法可以参考本人的最长不上升子序列 。

需要注意的是，本题要求的是严格上升序列的长度，即序列中不能存在值相等的元素。
因此对于某个值v,只有在v严格大于S[top]才可以S[++top]=v.
若小于等于S[top],则要在S中找大于等于v的S[t]，而不是大于v的。否则求出来的可能是最长不下降序列。

代码如下

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN (200000+10)

long N,K;
long v[MAXN];
long ans1,ans2;
long tmp[MAXN],len;

void init()
{
   scanf("%ld%ld\n",&N,&K);
   long i;
   for(i = 1;i <= N;i ++)
       scanf("%ld",&v[i]);
}

long lis()   //计算tmp中的LIS
{
   static long S[MAXN];
   long top = 1;
   S[top] = tmp[0];
   long l,r,mid,i;
   fprintf(stderr,"len %ld\n",len);
   for(i = 1;i < len;i ++)
   {
       if(tmp[i] > S[top])
           S[++top] = tmp[i];
       else
       {
           l = 1;
           r = top;
           while(l < r)
           {
               mid = (l + r) / 2;
               if(S[mid] >= tmp[i])
                   r = mid;
               else
                   l = mid + 1;
           }
           S[l] = tmp[i];
       }
   }
   return top;
}

void solve()
{
   long i;
   len = 0;
   for(i = 1;i < K;i ++)
       if(v[i] < v[K])    tmp[len ++] = v[i];
   if(len > 0)
       ans1 = lis();
   else
       ans1 = 0;
   len = 0;
   for(i = K + 1;i <= N;i ++)
       if(v[i] > v[K])    tmp[len ++] = v[i];
   if(len > 0)
       ans2 = lis();
   else
       ans2 = 0;
   printf("%ld\n",ans1 + 1 + ans2);
}

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

最长不上升子序列

题目描述：
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:
虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入数据:
第一行为一个整数 N,表示飞来的导弹个数,N<=100000
第二行为 N 个整数,依次表示导弹飞来的高度,高度数据为不大于 3000000 的正整数。
输出数据:
第一行,输出计算一套系统最多能拦截多少导弹
第二行,输出要拦截所有导弹最少要配备多少套这种导弹拦截系统。

容易看出，第一问求的是这个序列的最长不上升子序列的长度。这个问题有一个N^2时间规模的DP算法，用于10^5的数据是显然超时的。本人就不讲解这个算法了，不了解的读者可以自行搜索。

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

下面介绍一个时间复杂度为NlogN的，基于贪心和二分查找的算法。（h表示飞来导弹的高度）
引入一个数组S[MAXN],它的长度记作top。S[i]表示长度为i的最长不上升序列的末尾的元素的最大值。容易知道，S是不递增的。
初始化S[1] = h[0]，top = 1
从h[1]开始，依次处理每个导弹h[i]。如果h[i] < S[top],那么S[++top] = h[i]。否则用二分查找在S[1]~S[top]中寻找恰好小于h[i]的元素，并把它替换成h[i].
处理完所有h后，top的值即为最长不上升子序列的长度。

为什么可以这么做呢？本人认为有以下几个原因：
任何时刻均有i>=top;
对于一组数据，要获得较长的不上升子序列，则序列末尾的元素要尽量大。
把S中恰好大于h[i]的元素替换后，会给替换位置后的元素更大的上升空间，可能创造更长的序列。

一个问题：能否通过S和h两个数组，重构最长不上升序列呢？请读者思考。

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

题目的第二个问题是需要几套系统可以拦截所有导弹。对于这个问题，有一个贪心的解法。
用S[i]表示第i个系统目前的高度，初始化所有S[i]为LONG_MAX。
从h[0]~h[N-1]，对每个h[i]，都在S中找出恰好>=h[i]的S[k]，令S[k] = h[i]。
最后，统计S中小于LONG_MAX的值的个数cnt即为答案。

可以发现，对任意t，S[t]的值是只减不增的，并且S是具有单调性的，因此可以用二分优化查找。总的复杂度也是NlogN.

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

//nlogn的类LIS，贪心
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100005

long h[MAXN];
long S[MAXN];
long N;

void init()
{
   scanf("%ld\n",&N);
   long i;
   for(i = 0;i < N;i ++)
       scanf("%ld\n",h + i);
}

void solve_1()
{
   long i,top,l,r,mid;
   S[1] = h[0];
   top = 1;
   for(i = 1;i < N;i ++)
   {
       if(h[i] <= S[top])
           S[++top] = h[i];
       else
       {
           l = 1;r = top;
           while(l < r)
           {
               mid = (l + r) / 2;
               if(S[mid] < h[i])
                   r = mid;
               else
                   l = mid + 1;
           }
           S[l] = h[i];
       }
   }
   printf("%ld\n",top);
}

long find(long *v,long l,long r,long ele)   //二分查找
{
   long mid;
   while(l < r)
   {
       mid = (l + r) / 2;
       if(v[mid] < ele)
           l = mid + 1;
       else
           r = mid;
   }
   return l;
}

void solve_2()   //贪心地安排导弹，每次都使用恰好大于h[i]的导弹
{
   long i,x;
   static long v[MAXN];
   for(i = 1;i <= N;i ++)
       v[i] = 100000000;
   for(i = 0;i < N;i ++)
   {
       x = find(v,1,N,h[i]);
       v[x] = h[i];
   }
   for(i = 1;i <= N;i ++)
       if(v[i] == 100000000)    break;
   printf("%ld\n",i - 1);
}

int main()
{
   freopen("missile.in","r",stdin);
   freopen("missile.out","w",stdout);
   init();
   solve_1();
   solve_2();
   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; }