博文
Zoj 1013 Great Equipment(2008-02-21 19:09:00)
摘要：
2756964
2008-02-21 18:12:06
Accepted
1013
C++
00:03.02
2404K
C.D.=.=
有点意思的DP题，同样也有不小的难度。
模型大致如下：一组背包，除了体积以外，还有重量的限制。有3种不同的item：比如说一把剑，一件盔甲，一双鞋。他们各自有体积，重量，Def值，而组合到一起——也许叫做不死斗篷，出题者明显是英雄无敌的爱好者——又有新的Def加成。如何得到最大的Def？
对于每一辆车（背包），在装满的情形下，可以得到几组不同的xyz，代表三种装备的数量。假如能够得到所有车子总的xyz组合，这题就迎刃而解了。但是我们不能对100辆车子，对每种xyz之和进行搜索，这样数据量太大。
考虑到题目给出xyz<500，故而建立m[i][x][y]的数组，对前i辆车中的xy进行DP。因为在当前i车中，对于每组ix iy，都有唯一对应的iz（最大）。而只要把这辆车中的ixiy去掉就是前一辆车i-1下的xyz值，所以m[i][x][y] =MAX（m[i - 1][x - ix][y - iy]+iz），ix iy 遍历，表示在前i辆车中z能达到的最大值。从而所有的xyz组合都被记录下来了。这种用N-1维数组记录一个N维组合，然后对其DP求得最后一个数的方法就很棒。
为了节省空间，采用滚动数组。具体代码中把i-1提前，对于i-1下每一组xy，加上这辆车里的ixiy就是当前i组下的xy。
#include <cstdio>
#include <string>
#define min(x, y) ( x < y ? x : y )
#define rg(x, y) ( x = ( y > x ? y : x ) ) //replace if greater
int N, c1,&n......
Zoj 2527 Series(2008-02-19 19:30:00)
摘要：
2755219
2008-02-19 18:56:56
Accepted
2527
C++
00:00.07
4364K
C.D.
做了两天题后有点头昏脑胀，上星期连着熬夜看联盟杯的后遗症不失时机地蹦出来张牙舞爪。也罢，这个礼拜要好好休息，不看冠军杯了。 （其实上个赛季也都是看Bt录播，人懒没药医 =.= ）
一道简单的DP。难点在于原来的算法时间复杂度O(N^3)，N=1000。
题目描述相当简单，给定一个数组，求其中最长的等差数列的长度。
首先考虑一维规划。显然不行，一个等差数列不能用一个数字进行定义。转而考虑二维。当数列的差不大时，可以考虑用F(i,d)表示当前一个数a[i]下等差为d的数列长度。可是这个数列给出了1e10的范围……
继续转进。F(i,j)表示数列的最后一个数是a[i],倒数第二个是a[j]。这样就保存了等差，也可以求得倒数第三个数，前提是找得到。只要在数组里找到它的位置k，就可以继续方程式：F(i,j) = F(j,k) + 1。
但是这样一来无疑要遍历整个数组，使O上升到N^3，这太慢了。为此先对整个数组排序，去除重复的数字，然后在有序的数组里可以用二分搜索k。O(N^2*log(N))，完全满足时间要求。
#include <cstdio>
#include <string>
#include <cstdlib>
int b[1001][1001], a[1001], N, ans;
int cmp ( const void *a, const void *b )
{
return *( int * ) a > *( int * ) b;
}
int init ();
int b_search ( int, i......
Zoj 2278 Fight for Food(2008-02-11 14:50:00)
摘要：
2745991
2008-02-07 15:05:00
Accepted
2278
C++
00:00.68
1708K
C.D.
感谢W111（WCY）同学的解题报告。
相当出色的DP优化题。
类似于最大不下降子序列，一般有O(N2)的简单算法。但N>30000，故需要优化。原先的算法中，设F(i)= 到第i只老鼠时捕捉到的最大数目，F(i)= max(F(j)+1)，j从1到i-1，假如在时限内能从第i到第j只老鼠出现的方格。这里可以预先使用BFS，用time[rati.i][rati.j][ratj.i][ratj.j]来记录从i到j的最小时间，并加以判断。
为了优化时间，首先进行预处理，把不可能捕捉到的老鼠删除，把从每一点访问所有点至少需要的时间maxtime[rati.i][rati.j]记录下来。
然后把老鼠出现的时间排序。当j从1到i-1访问的时候，可以看到有一些老鼠和当前i的时间相差太多，必然可以访问。这样只要把这些老鼠的最大值+1即可。这些老鼠是：
设老鼠j到老鼠i的时间大于i访问所有点的最大时间maxtime。那么，对于k<j，也必然大于maxtime。
这样就成功剪去大部分时间。
WA了无数遍，终于发现漏了一种不可能捕捉到老鼠的状况。
另外试验一下代码格式
/**//*
作者： Crux.D
日期： 2008-2-11
描述： 动态规划的优化
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#d......
Zju 1800 Decorations(2007-04-30 22:53:00)
摘要： 最近经常性地在关键时刻掉链子。古希腊先哲说，人不会两次跌进同一个坑——确实，我跌进了两个坑，摔的鼻青脸肿。先是在杭电邀请赛上看错范围，把辅助数组开小，幸好同伴火眼金睛；这道题犯的错误几乎一摸一样，一个a[601][101]的数组开成了a[101][601]。最可恨的是这样的错误假如没有意识到，一辈子都找不出来！ZOJ上wrong answer映的我发绿，莫名其妙，怎么也该打出一个RunTimeError吧……结果我的程序几乎被改成BusyCai同学的程序了……
这类词典型的dp题目倒也差不多，a[i][k]代表了第k个词语在填入第i个位置时的可能总数。只要扫描上一个位置的所有M词语a[i- 1][j]，满足情况者加入a[i][k]即可。BusyCai的写法比较好，用每个位置a[i][k]去加到下一个位置a[i + 1][j]。a[i][k]可能为0，节省了很多时间。
#include <cstdio>
#include <string>
int N, L, M, len, a[110][610];
char str[610][11];
void init ()
{
int i;
for ( i = 0; i < M; i ++ )
{
scanf ( "%s", str[i] );
}
memset ( a, 0, sizeof ( a ) );
len = strlen ( str[0] );
}
int check ( int a, int b )
{
int i;
for ( i = 1; i < len; i ++ )
{
if ( str[a][i] != str[b][i - 1] )
return 0;
}
return 1;
}
void dp ()
{
int i, k, ......
Zoj 2422 Terrible Sets(2007-03-02 15:31:00)
摘要：此题是zoj1985的变种。
1985的每个小矩形没有宽度w，只有高度h。故加入计算从第x1到第xn个矩形的w总和。对于每个小矩形i，求以其为最小基准左右能到达的位置，然后计算总面积。
其中cqf用迭代求左右两侧最多能到达矩形的方法尤为经典。
#include <cstdio>
#include <string>
typedef struct
{
int w, h;
} Rect;
Rect a[50001];
int n, l[50001], r[50001], s[50001];
void pt ( int i )
{
printf ( "l%d r%d s%d h%d\n", l[i], r[i], s[r[i] + 1] - s[l[i]] , a[i].h);
}
int main ()
{
//freopen ( "in.txt", "r", stdin );
while ( scanf ( "%d", &n ) && n != -1 )
{
int i, ii, sum = 0;
s[0] = 0;
for ( i = 0; i < n; i ++ )
{
scanf ( "%d %d", &a[i].w, &a[i].h );
sum += a[i].w;
s[i + 1] = sum;
}
for ( i = 0; i < n; i ++ )
{
ii = i;
while ( ii > 0 && a[i].h <= a[ii - 1].h)
&nbs......
Zju 2059 The Twin Towers(2007-02-18 16:35:00)
摘要：最近几天在研究usaco，那是一个很有趣的地方，做起题来像通关游戏，所以zoj倒做得少了。不有趣的地方是一旦一道题解不出，就像碰到一位大Boss，死打也不扣血，非得你跑到城外去拼命练级方可过关。于是回过头来写写以前没做出的几道简单dp题，这就是其一。
题目的大意如下：有一列N个水晶，把他们搭成双子塔，要求塔高一样，求塔的最大高度。当初做的时候不小心看错了条件，以为每块水晶最大高度是2000，接着开了个200000的数组，自己机子都过不了。今天看了busycai的程序，才明白搞错了。总高度是2000，所以O(n) = N×2000.时间还算不错。
起初想用b[i]来表示塔高为i的某种状态（塔高之差？或是别的什么），结果想了半天不得其解。其实把设定倒过来，当bi表示塔高之差为i的时候，对总高度dp，这样就简单了。
对0<= i <= 2000，当在左或右边放入a[k]之后，差有两种可能，i + a[k], i - a[k]。然后更新，即可。
#include <cstdio>
#include <string>
int abs ( int i )
{
return i > 0 ? i : -i ;
}
int N, a[101], b[2][2001], p;
int main ()
{
//freopen ( "in.txt", "r", stdin );
while ( scanf ( "%d", &N ) && N >= 0 )
{
int i, end, j, k;
for ( i = 0; i < N; i ++ )
{
&......
Zju 1787 Tiling Up Blocks(2007-01-27 22:25:00)
摘要：这道题相当的经典，本身就有很多做法，而CQF大牛的做法尤为精妙。
给出一系列零件Si，零件有两个参数Ai Bi。现在将其排序，要求若i>j，则Ai>=Aj Bi>=Bj。也就是前面的两个参数要分别小于等于后面的两个参数。求此队列的最大长度。
那么如果将其投影到二维平面上，对每个零件Ai Bi点计数，那么问题就转换成为从最左下的1 1到左上的100 100，只能向右和向上运动，求运动过程中的访问总和最大值。
因此只要把每个点下面和左面的点比较，大者记入此点总和即可。
今天偶然看了一下排名，ZOJ果然有没落的倾向，而据说POJ越来越繁荣了。
#include <cstdio>
#include <string>
int n, a[101][101], b[101][101], nx, ny, mx, my;
int maxi ( int a, int b )
{
return a > b ? a : b;
}
void pb ()
{
//printf ( "%d %d %d %d\n", mx, my, nx, ny );
int i, k;
for ( i = nx; i <= mx; i ++ )
{
for ( k = ny; k <= my; k ++ )
{
printf ( "%d ", b[i][k] );
}
printf ( "\n" );
}
}
void init ()
{
memset ( a, 0, sizeof (a) );
memset ( b, 0, sizeof (b) );
mx = my = 0, nx = ny = 101;
}
int dp ()
{
int i, k;
for ( i = nx; i <= mx; i ++ )
&nb......
Zju 1638 Greedy Island(2007-01-24 13:43:00)
摘要：以下是xavier_lt的解题报告。稍微分析一下，不难发现O(nabc)的DP方程：f[0,0,0]=0;f[i,j,k]=max{ f[i-1,j,k] + attack[i+j+k], f[i,j-1,k] + defence[i+j+k], f[i,j,k-1] + special[i+j+k] }这样，求总的属性值只要加一个第二关键字c[i,j,k]就可以了。但是通过题目，发现N是一个很大的数，于是用这种方法将会非常慢!但是，很显然有一些牌是可以完全忽略掉的，就像[0,0,0]这样的牌。要怎么删掉一定不需要的牌呢？令S=a+b+c，则对于每种属性，只需要前S张即可了，而总计只需要3S<=300张牌。这样优化后，算法的速度就会大大的提高了，优化后的时间复杂度是O(nlgn+min(n,3s)*a*b*c)。-------------------------------------------------------------------我只看的懂这些了。但是这个办法真的很经典，一道难题就这样变成了O(1004)的简单题。-------------------------------------------------------------------进一步分析，此题的总属性值不会超过300*100，个体属性值不会超过100*100，所以，可以建立一个二分图来解决此题。令左边为N个红节点（攻击属性），N个黄节点（防御属性），N个蓝节点（特殊属性），右边是A+B+C个节点，第I个红节点到第J个右节点的边权为Attack[I]*100000+Attack[I]+Defence[I]+Special[I]，同理建立其他颜色的左节点到每个右节点的边。这样我们只需对这个二分图求最大全匹配就可以了，复杂度将会下降到O(nlgn+min(n,3s)*(a+b+c)^2)，优化后的时间还是很不错的^_^。
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
#define S 102
#define SS 100001
int opt[S][S][S], sum[S][S][S], n, a[SS],......
Zju 1349 Four Quarters(2007-01-23 15:07:00)
摘要：A分布
Player B
Player A
HH
HT
TT
HH
1
1
2
HT
0
0
1
TT
-1
0
0
B分布
Player B
Player A
HH
HT
TT
HH
0
-1
-1
HT
1
0
0
TT
2
0
-1
A和B在此分布下进行20轮累计，求每轮分数的胜负概率。第一次做的时候以为A和B是独立的，分别计算他们得分的概率，再计算大小，结果第一轮的数据就卡住。然后想到了一个取巧的办法，把A和B的得分相减，得到一个新的分布，最后判断总分是否大于0。
随便说一句，我的代码风格向软件工程的标准又迈进了一步，这是人类的一小步，却是我的一大步。
#include <cstdio>
#include <string>
#define def 100
double p[7], s[2][200];
int mx, mn;
void ps (int c)
{
int i;
double sum_w, sum_l, sum_t;
sum_w = sum_l = sum_t = 0;
for ( i = mn - 3; i <= mx + 3; i ++ )
{
if ( i > def )
sum_w += s[0][i];
if ( i < def )
sum_l += s[0][i];
if ( i == def )
sum_t += s[0][i];
}
printf ( "%5d%10.4f%%%9.......
Zju 1642 Match for Bonus(2007-01-23 00:04:00)
摘要： 这是一题典型的最大公共子序列。一开始没看出来，直到写dp写不下去，赶紧去翻busycai大牛的程序才恍然大悟。
用f[i][k]表示a取到i，b取到k时最大的权值。f[i][k] = max (f[i - 1][k - 1] + v[i], f[i][k - 1], f[i - 1][k])。其中第一个表示i和k时取到相同的字符。
#include <cstdio>
#include <string>
int v[501], n, ans, f[2001][2001], len;
char str[2][2001];
int dp ()
{
int i, k;
len = strlen (str[0]);
memset (f, 0, sizeof(f));
for (i = 1; i <= len; i ++)
{
for (k = 1; k <= len; k ++)
{
if (str[0][i - 1] == str[1][k - 1])
{
f[i][k] = f[i - 1][k - 1] + v[str[0][i - 1]];
}
int mx = f[i - 1][k] > f[i][k - 1] ? f[i - 1][k] : f[i][k - 1];
if (mx > f[i][k]) f[i][k] = mx;
}
}
return f[len][len];
}
int main ()
{
//freopen ("in.txt", "r", stdin);......