博文
HDU 1053 Advanced Fruits (DP)(2009-07-11 16:32:00)
摘要：和算法书上讲的那个最大公共了串是一样的。
一开始tl了几次。因为忘记d[i][j]=0的这种情况了！
f[i][j]保存的是a的前i个字符和b的前j个字符的最大子串。
d[i][j]保存的是最大值是如何得来的。d[i][j]=0表示到目前为止还没有相同的子串
d[i][j]=1表示a[i]==b[j]
d[i][j]=2表示从左得来
d[i][j]=3表示从上得来
#include<stdio.h>#include<iostream>#include<string.h>int f[105][105];int d[105][105];using namespace std;int main(){ int len1,len2,i,j,len; char a[105],b[105]; char c[210]; while(scanf("%s%s",a,b)!=EOF) { len1=strlen(a); len2=strlen(b); for(i=0;i<len2;i++)//初始条件 { if(a[0]==b[i]) { f[0][i]=1; d[0][i]=1; for(i++;i<len2;i++) { f[0][i]=1; d[0][i]=2; } break; } else{ f[0][i]=0;d[0][i]=0;} } for(i=0;i<len1;i++) &......
hdu 1024 DP(2009-07-10 20:25:00)
摘要：经典的DP题
状态方程 d[i][j]=max{d[i][j-1],d[i-1][t]} i<t<jn很大，这样的数组开不了！
d[i][j]的值只用到d[i][j-1],d[i-1][j]
所以用两个一维数组表示
b[],c[]
解决上式用了三重循环。铁定超时。
所以第二重循环中用c［］记录max{d[i-1][t]},i<t<j;
这样时间复杂度就降低了
程序：
#include<stdio.h>#include<string.h>#include<malloc.h>//#include<limits.h>#define MAX1 1000000long a[MAX1];long b[MAX1];long c[MAX1];int main(){ long i,j,m,n; long max,sum; while(scanf("%d %d",&m,&n)!=EOF) { memset(b,0,(n+1)*sizeof(b[0])); memset(c,0,(n+1)*sizeof(c[0])); for(i=1;i<=n;i++) scanf("%ld",&a[i]); b[0]=c[1]=0; for(i=1;i<=m;i++) &nbs......
HDU 1080 Human Gene Functions(2009-07-10 09:51:00)
摘要：英文的一开始没看懂题。baidu一下看了别人的翻译才知道是很简单的一道动规题
和算法书里的最长公共子序列很类似
题目意思是两个字符串si和sk，每个字符匹配都有一个权值，要求他们的最大匹配权值
f[i][j]表示串A前I个字符和串B前J个字符匹配的最大权值。则有状态转移方程：
f[i][j]=max{f[i-1][j-1]+stand[a[i]][b[j]],f[i-1][j]+stand[a[i]][5],f[i][j-1]+stand[5][b[j]]};
程序如下：
#include<stdio.h>int stand[6][6]={{0,0,0,0,0,0}, {0,5,-1,-2,-1,-3}, {0,-1,5,-3,-2,-4}, {0,-2,-3,5,-2,-2}, {0,-1,-2,-2,5,-1}, {0,-3,-4,-2,-1,-100000}};char ch;int f[105][105];int a[105],b[105];int main(){ int N,n1,n2,i,j; scanf("%d",&N); while(N--) { scanf("%d%c",&n1,&ch); for(i=1;i<=n1;i++) { scanf("%c",&ch); if(ch=='A') a[i]=1; else if(ch=='C') a[i]=2; else if(ch=='G') a[i]=3; else if(ch=='T') a[i]=4; } scanf("%d%c",&......
HDU 1074(2009-07-09 20:38:00)
摘要：Doing Homework
Problem Description
Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework). Note: All the su......
搬寝室(2009-07-09 17:22:00)
摘要：搬寝室
杭电1421
Problem Description
搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.
Input
每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).
Output
对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.
Sample Input
2 1
1 3
Sample Output
4
没得说的动态规划/
f[i][j]数组保存的是在第i个数据前选j对的最小疲劳度/
方程：f[i][j]=min{f[i-1][j],f[i-2][j-1]+(a[i]-a[i-1])^2}
代码：#include<stdio.h>#include<stdlib.h>int a[2002];int f[2002][2002];int cmp(const void *a,const void *b){ return *(int *)a-*(int *)b;}int main(){ int n,k,kk; int i; while(scanf("%d%d",&n,&k)!=EOF) { for(i=0;i<n;i++) scanf("%d",&a[i]); ......
milliard Vasya 函数(2009-05-31 19:37:00)
摘要：milliard Vasya 函数Time Limit:1000MS Memory Limit:16384KTotal Submit:65 Accepted:9 Description Vasya是一个刚入门的数学家。 他决定对科学做出一个重要的贡献，以便世界知名。 但怎么才能做到呢？像勾股定理那样有趣的事实都已经被证明过了。 对！他要做出一些他自己的东西，原创性的。 因此他想出了一个Vasya函数定理。 Vasya函数（VF）相当简单：第N个VF函数在点S的值，就是从1到N之间的整数当中，各位数字之和等于S的数的个数。 Vasya给你一个任务，找到milliard VF值，即 N = 1000000000 时的VF值。Input 整数S (1 ≤ S ≤ 81)Output milliard VF 在 S 点的值。Sample Input 1Sample Output 10Source 想法超级笨，先算出来，放到数组里，这样就避免超时了，哈哈常用方法 import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static int n,number;
private static int i;
private static int i1,i2,i3,i4,i5,i6,i7,i8,i9;
private static int []a={0,10,45,165,495,1287,3003,6435,12870,24310,43749,75501,125565,202005,315315,478731,708444,1023660,1446445,2001285,2714319,3612231,4720815,6063255,7658190,9517662,11645073,14033305,16663185,19502505,22505751,25614639,28759500,31861500,34835625,37594305,40051495,42126975,43750575,44865975,454338......
不幸运车票(2009-05-31 19:35:00)
摘要：不幸运车票
Time Limit:1000MS Memory Limit:16384KTotal Submit:78 Accepted:8
Description
莫斯科住着些奇怪的人。 每次乘公车，买一张带有6位数的票，他们把前3位数字和后3位数字加在一起。 如果这两个和相等，他们认为这张票是幸运票。 一个拥有幸运票的人，梦想什么事，吃掉这张票（不，它不是用巧克力做的，是纸），梦想就会成真...至少他们相信如此。 圣彼得堡也有一些奇怪的人。 每次乘公车，买一张带有6位数字的票，他们试图把奇数位的3个数字和偶数位的3个数字加起来。 如果这两个和相等，他们认为这张票是幸运票。 一个拥有幸运票的人，梦想什么事，吃掉这张票（圣彼得堡的车票也不是用巧克力做的，是纸），梦想就会成真...至少他们相信如此。 在“第3首都”— 叶卡特琳堡 — 我们嘲笑这些奇怪的想法。 我们很实际，我们不迷信，一点也不。 但我们懂得太多的幸运不是好事。 因此，如果一张票在“莫斯科意义”下和“圣彼得堡意义”下都是幸运票，我们认为它是不幸运票。 如果我们乘车买到一张不幸运车票，我们会扔掉它，立即下车。 不幸运票的两个例子是 472175 和 810513。 你要写一个程序，计算全部N-位不幸运票的数目。
Input
输入包含一个正偶数 N (2 ≤ N ≤ 20) — 车票号码的数位。 注意，00742544 是有效的8位车票 （它是一张圣彼得堡幸运票）。
Output
你的程序应该输出一个整数，N位不幸运车票的总数。
Sample Input
4
Sample Output
100
Source
代码写的很变态！其实想法很简单。难得优化了。import java.math.BigInteger;
import java.util.Scanner;
public class Main {
private static int n;
private static BigInteger f(int x){
int i,i1,i2,i3,i4,i5;
BigInteger total=new BigInteger("0");
int number=0;
if(x==0) return BigInteger.O......
科学会议(2009-05-31 19:32:00)
摘要：科学会议
Time Limit:1000MS Memory Limit:16384KTotal Submit:95 Accepted:3
Description
科学会议的功能通常分为同时进行的几个分区。 例如，一个区关于并行计算，一个区关于可视化，一个区关于数据压缩，等等。 显然，若干分区的工作同时进行是必要的，以便缩减会议科学议程的时间，从而有更多的时间进行宴会，饮茶及必要的讨论。 因而，一个人感兴趣的多个报告在不同的分区同时进行是可能的。 一位与会者写出一个关于所有他感兴趣的报告的时间表。 他要求你算出他能够出席的报告的最大数目。
Input
第一行包含数字N（1 ≤ N ≤ 100000），感兴趣报告的数目。 接下来的每行包含两个整数 Ts 和 Te (1 ≤ Ts < Te ≤ 30000)，用空格分开，表示相应报告的起始和结束。 时间以距会议开始的分钟数表示。
Output
输出该与会者能够出席的报告的最大数目。 与会者不能出席两个同时进行的报告。 并且他出席的任意两个报告之间的时间间隔至少1分钟。 例如，如果他能够出席的一个报告在15分钟结束，则下一个报告必须在16分钟或更晚。
Sample Input
5
3 4
1 5
6 7
4 5
1 3
Sample Output
3
Source
校赛题目，很简单的一道DP题目，可惜比赛时没做出来，其实现在就算是AC了。我也觉得比赛时我没做错，是给的测试数据的问题。很郁闷
状态方程很简单：
f[i]=max{f[i-1],f[m.x-1]+1}
m.x表示i分钟结束的报告的开始时间#include<stdio.h>
#include<stdlib.h>
int f[30005];
struct node
{
int x,y;
}m[100004];
int cmp( const void *a , const void *b )
{
struct node *c = (node *)a;
struct node *d = (node *)b;
if(c->y != d->y) return c->y - d->y;
el......
畅通工程(2009-05-29 14:50:00)
摘要：畅通工程Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4521 Accepted Submission(s): 2184
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1这种输入也是合法的当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
Sample Output
1
0
2
998
HintHint
Huge input, scanf is recommended.
Source
杭电ACM集训队训练赛（I）
Recommend
JGShining
简单，练练手，哈哈，
#include<stdio.h>int mark[1004];int flag[1004];int main(){ int i,j,number,a,b,N,M,temp; while(scanf("%d",&N)!=EOF) { if(N==0) break; &nbs......
还是畅通工程(2009-05-29 13:06:00)
摘要：还是畅通工程Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3294 Accepted Submission(s): 1565
Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
HintHint
Huge input, scanf is recommended.
Source
杭电ACM集训队训练赛（I）
Recommend
JGShining#include<stdio.h>int f[10000][3];int mark[108];int main(){ int N,a,b,len,min,mini; int i,j,temp,totallen,totalnum; int MAX; while(scanf("%d",&N)!=EOF) { if(N==0) break; for(i=......