博文
Zju 1387 Decoding Morse Sequences(2007-01-21 21:43:00)
摘要： 老实的说，我对自己解出这道题并不抱很大的希望——不比今天上午的考试及格的概率大。众所周知，今天是研究生入学考试的第二天，上午这门是最头疼的数学，高考那年的数学就特别难……当然这和我的人品没有半点联系。
幸好我对这门课的期望值相当的低。每次我很低调地打出我的数学宣言，周围总是用看野生大熊猫的目光看着我。本来这种行为相当低调，当重复了一百遍以后就变成了高调。所以我的希望是数学要么就考中考卷——我中考很不谦虚地拿了全市第一，但是我怕让我现在去考也会落榜；要么就越难越好，要死一起死。
我的祈祷果然生效了。当我做到大题第二题的时候，我还信心满满，想象着浙大的幸福生活。
要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎要谨慎。
我低声告诫自己，一边翻开第三题。不会做——不要紧。第四题，做不来。还有四题。我向来保持革命乐观的精神，这是江总的教导。
当我把整张试卷全部翻阅一遍，突然发现自己能做的不过区区七、八十分时，革命精神立刻被轰到片·甲·不·留。呜呜呜，我要回家找妈妈。
当然，这同样和我的人品没有任何联系。我现在只希望两件事。
一、数学分数线被轰到最低。
二、让——我——过——线。
罗里八索地扯了一大堆。正题只写两句话 = =
1.把字典里的char*变成莫尔码。
2.对要求的morse码dp。
#include <cstdio>
#include <string>
char tran[26][5] = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..",
&n......
Zju 1163 The Staircases(2006-12-18 23:19:00)
摘要：
2174729
2006-12-18 23:13:20
Accepted
1163
C++
00:00.02
2384K
Crux.D
很好的一道dp题，积压已久。这让我想起小学生时代的作文了：
“今天我又做了一件好事，我真高兴呀。”
这道题的陷阱是大数，用double即可避过。方程是b[i][k] = b[i - k][k - 1]，i代表N，k代表最高层的块数。然后把b[i][k]累加起来就可。
另外这题只用了23行，和今天做的另一道题1111比起来，简直是他喵的奇迹。那道题整整花了我半个下午，调试了3次，写了400多行……
#include <cstdio>
#include <string>
double a[505][505];
int main()
{
int i, k, n;
memset(a, 0x00, sizeof(a));
a[0][0] = 1;
for(i = 0; i < 505; i ++)
{
for(k = 1; k <= i; k ++)
a[i][k] = a[i - k][k - 1] + a[i][k - 1];
for(k = i + 1; k < 505; k ++)
a[i][k] = a[i][i];
}
while(scanf("%d", &n) && n)
{
printf("%0.0f\n", a[n][n] - 1);
}
return 0;
}
----------------------------
对比的程序，zju 1111
#include <......
Zju 2402 Lenny's Lucky Lotto Lists(2006-10-22 16:46:00)
摘要：
2113146
2006-10-22 15:53:31
Accepted
2402
C++
00:00.19
1988K
Crux.D
最近偏爱这类题目。当然，这题的Accepted Submit也相当的多。对这类题，我的原则是，宁可错杀一万，不可放过一个。对于弱题天生的嗅觉。
......然而事物的现象和本质永远都是有差距的。这句话在哪里都适用。想算法用了10分钟，修改和提交用了整整1个钟头。题目如下。
给定两个数N和M。比如4和10。求序列An的个数。序列An从某个正整数开始——比如1，每个数都要>=前一个数的2倍，最后一个数<=M，序列长度为N。
但是我还是偷懒了。一般的讲，看到题目以后，尤其是长且欠的题目，我的第一反应一定是打开译题站，然后输入题号，搜索。这除了降低我的英语阅读能力和增强我对于网络的依赖性以外没有任何好处。然后我的第二反应就是看贴，不自觉，或者自觉的。接下来第三步，我看到了标准解法......幸好很多题目我还看的懂。今天我只瞄到了两个字：dp。
......OK，那么dp吧。
其实就像fatboy大人讲过的，dp只是一种思路，并不是一种算法。当我们不把dp当成dp的时候，我们自然就会dp了。
停。我不是杨过。我不会武功。还是讲讲思路吧。
还是拿4，10做例子。
这个例子里，我们能组成4个序列。
1,2,4,8
1,2,4,9
1,2,4,10
1,2,5,10
我的直觉告诉我，一定有递推关系。（......好吧，是帖子告诉我的）首先否决的是搜...搜索。N= 50, M= 2000，C(50,2000) = ∞，四核CPU都不够用。我很快想到了......
Zju 1245 Triangles(2006-10-20 23:17:00)
摘要：
2111683
2006-10-20 22:42:27
Accepted
1245
C++
00:00.12
1004K
Crux.D
1245是一道比较经典的dp。一个大的正三角形，由许多小的三角形组成，他们分为黑白二色。求最大的白色正三角形面积。
思路不难。把每一行白色的累计数存起来作dp。当然这要分尖朝上的和尖朝下的。朝上的公式是r[i][k] = min(r[i - 1][k - 1] + 1, b[i][k]); b存的是白色的累计数，r是最终的边长。朝下的亦同。
似乎很简单。可好久没做题了，犯了些低级失误，比如把b和r写反了。我不知道这和越来越近的考研有什么关系——也许我就是在岩壁上紧抓藤蔓的失足者，寒冷的1月就是悬崖下的毒蛇。
所以......还是要加油了。藤蔓不是这么可靠的，我的数学也一样。
附程序，写的比较烂，仅供参考。
#include <iostream>
#include <cstring>
using namespace std;
int n, b[101][210], r[101][210], ans;
int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
//freopen("in.txt", "r", stdin);
int i, k, c = 1;
while(cin >> n && n)
{
memset(b, 0, sizeof(b));
memset(r, 0, sizeof(r));
printf("Triangle #%d\n", c ++);
for(i = 1; i <= n; i ++)
......
Zju 1234 Chopsticks(2006-08-31 00:38:00)
摘要：
2049042
2006-08-31 00:00:06
Accepted
1234
C++
00:00.39
448K
St.Crux
题意：3个数一套，(a1≤a2≤a3)，并定义c =(a1 - a2)^2 。在M个已排序数里找出N套这样的数，使得∑c最小。
典型的组合式dp题。这题的关卡在于：数是一套的，而不是一个，而第三个数又是无用的。但是有一点：a1和a2必然是临近的数，(不然必大于这种最优选择)即取到第k个数时，对于ak和ak-1只有两种选择：
1.不取。2.取。(........) 捆绑考虑。
和所有的组合dp一样，可以列出方程：
opt[i, k] = opt[i - 1, k - 2] + (ak - ak-1)^2 (1≤i≤n, 1≤k≤m)
且opt[i, k] = opt[i, k - 1]
其中opt表示前k个数里取i个能取到的最小值。其中k对于每个i都有取值范围，两边都有，这个和组合dp一样，只不过稍显复杂一些。
而这显然要优化，数组开这么大，1000×5000，还好现在内存便宜。但是还得优化，n值一大照样破产。
那么，只需要两个数组便可。这个也是老规矩了，上一步的先存在b[0]里，每个做完了放b[1]里，等k循环完一遍就可把b[1]赋值给b[0]。这是一种经常用的手法，也是所有不写注释的程序最让人百思不得其解的地方。
#include <cstdio>
#include <string>
#define MX 99999999
int a[5001], b[2][5001], c, n, m;
void init()
{
memset(b, 0, sizeof(b));
}
void dp()
{
int i, k;
for(i = 1; i <= m; i ++)
{
for(k = 2 * i; k <= n; k ++)
{
b[1][k] = MX;
if(k > 2 * i......
Zju 1425 Crossed Matchings(2006-08-21 15:49:00)
摘要：
2035433
2006-08-21 15:25:00
Accepted
1425
C++
00:00.01
432K
St.Crux
这是一道典型的dp题。ZC的解题报告告诉我.......
自己看吧。辛辛苦苦写了15分钟的我的解题报告被Maxthon的鼠标手势给毁了，我真倒霉。
我的算法更加保险，也可以理解为更加笨拙。有一点不明白的地方是为什么他可以用该杀的贪心？这怎么可以用贪心？呜......我就等于O(n^4)了。
#include <cstdio>
#include <string>
int n, an, bn, a[101], b[101], r[101][101];
void dp()
{
int i, k, mx, j, u;
memset(r, 0, sizeof(r));
for(i = 1; i <= an; i ++)
{
for(k = 1; k <= bn; k ++)
{
mx = 0;
if(a[i] != b[k])
{
for(j = i - 1; j > 0; j --)
{
if(a[j] == b[k])
{
for(u = k - 1; u > 0; u --)
{
if(b[u] == a[i])
{<......
Zju 1027 Human Gene Functions(2006-08-14 18:05:00)
摘要：
2021057
2006-08-14 17:39:09
Accepted
1027
C++
00:00.01
428K
St.Crux
两个字符串si和sk，每个字符匹配都有一个权值，要求他们的最大匹配权值。
很久以前在论坛上看过介绍，说和求最长子序列十分类似，因此很快就联想到了dp:)
事实上，这个题和LCS......确实很相似。同样是用一个二维数组来表示si的前i个数与sk的前k个数（字符）匹配的最大值，同样在f(n, m)处得解。不同的是LCs求的是最大长度，而这个求的是最大值。
所以用从下向上递推的思想分析。比如si＝AT，sk＝TA。当A和T匹配后，显然有一种情况：f(2, 2) = f(1,1) + a[2][2]； 那么移一位如何？即把si的T移动到TA的后面，使A和TA匹配，得f(2, 2) = f(1, 2) + T与-的匹配值。同理可得其他情况，在这些情况中取最大值即可。
#include <cstdio>
#include <string>
int a[5][5] = { {5, -1, -2, -1, -3}, {-1, 5, -2, -3, -4}, {-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1}, {-3, -4, -2, -1, 0} }, b[101][101], s0[101], s1[101];
int n, m, t, ans;
int mx(int a, int b, int c)
{
if(a >= b && a >= c)
return a;
if(b >= a && b >= c)
return b;
if(c >= a && c >= b)
return c;
else
return -99999999;
}
void read()
{
char tc; int k;
sca......
Zju 1196 Fast Food(2006-08-06 23:54:00)
摘要：
2004112
2006-08-06 23:32:06
Accepted
1196
C++
00:00.02
704K
St.Crux
dis[i][k]表示在前k+1个加油站(0-k)中放入(i+1)个补给站所最小达到的距离和。
cost[i][k]表示从点i到点k所需要的最短距离，当且仅当补给站放在i，k的中点时。
方程是dis[i][k] = min(dis[i - 1][j] + cost[j + 1][k]) i - 1 <= j <k
C++的数组下标真是头痛哪
#include <cstdio>
#include <string>
#include <cmath>
int d[201][201], s[201][201], a[201], n, m;
#define MX 99999999
int main()
{
//freopen("in.txt", "r", stdin);
int c = 0;
while(scanf("%d %d", &n, &m) && n)
{
printf("Chain %d\n", ++ c);
int i, k, j;
for(i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
}
memset(s, 0, sizeof(s));
for(i = 0; i < n; i ++)
{
for(k = i; k < n; k ++)
{
int mid = (i + k) / 2;
&nb......
Zju 1524 Supermarket(2006-08-06 15:46:00)
摘要：
2003120
2006-08-06 15:30:49
Accepted
1524
C++
00:00.27
400K
St.Crux
这个题是典型的dp。n = 100, m = 100000，一开始打算对m进行dp，结果显然超时。后来看了几个帖子，明白是对n进行dp，以每一步的总和为状态转移，方程如下：
p(N) = min(p(N - 1) + di, p(N)) p(N) ≠ 0
di p(N) = 0
#include <cstdio>
#include <string>
double a[100];
int b[100], n, m, mx, tmx;
int main()
{
int i, k;
//freopen("in.txt", "r", stdin);
while(scanf("%d %d", &n, &m) && n)
{
memset(a, 0, sizeof(a));
for(i = 0; i < n; i ++)
{
&......
Zju 1366 Cash Machine(2006-08-04 23:05:00)
摘要：
1999291
2006-08-04 22:51:44
Accepted
1366
C++
00:01.23
1176K
St.Crux
终于又ac了一题.....最近几天我被淹没在绿色的wrong answer里。
『这个题很经典』hysbz的admin如是说。但我还是用不那么经典的办法.....用了两个数组，一个存标志位一个存数据。那个排序可有可无。
#include <cstdio>
#include <string>
int a[100001], b[100001], c, n, mx;
int ni[10], di[10];
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d", &c) != EOF)
{
int i, k, j;
scanf("%d", &n);
for(i = 0; i < n; i ++)
{
scanf("%d %d", &ni[i], &di[i]);
}
for(i = 0; i < n - 1; i ++)
{
int j = i, t0 = di[i], t1 = ni[i];
for(k = i + 1; k < n; k ++)
{
if(t0 > di[k])
{
j = k; t0 = di[k];
}
}
&nbs......