终于开始DP了】
HDOJ_1159 Common Subsequence
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
子结构特征：
lf(i,j)= f(i-1,j-1)+1 (a[i]==b[j])
max(f(i-1,j),f(i,j-1)) (a[i]!=b[j])
由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有关, 而在计算f(i,j)时,
只要选择一个合适的顺序, 就可以保证这三项都已经计算出来了,
这样就可以计算出f(i,j). 这样一直推到f(len(a),len(b))就得到所要求的解了.
#include <stdio.h>
#include <string.h>
int main() {
int t,i,j,lena,lenb;
char a[],b[];
int map[][];
while(EOF != scanf("%s %s",a,b)){
lena=strlen(a);
lenb=strlen(b);
memset(map , ,sizeof(map));
for(i=;i<=lena;i++){
for(j=;j<=lenb;j++){
if(a[i-] == b[j-])
map[i][j] = map[i-][j-] + ;
else if(a[i-] != b[j-]){
int temp = map[i-][j];
if(map[i][j-] > temp)
temp = map[i][j-];
map[i][j] = temp;
}
}
}
printf("%d\n",map[lena][lenb]);
}
return ;
}
HDOJ1003
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence.
For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
#include <stdio.h>
#define MAX 100005
int nNum[MAX];
int start, end;
//算法思路:用sum和max来记录临时最大和最终最大
//而start end ts te 分别用来记录起点 终点 临时起始点 终点
int cal(int len){
int max, i, sum, ts, te;
sum = max = -; //让max和sum开始置于无限小
for(i = ; i < len; i++){
if(sum < ){
if(nNum[i] > sum){
sum = nNum[i];
ts = te = i;
if(max < sum){
max= sum;
start = ts;
end = te;
}
}
}else{
sum += nNum[i];
te = i;
if(sum > max){
max = sum;
start = ts;
end = te;
}
}
}
return max;
}
int main(){
int t, i, n, j;
while(EOF != scanf("%d", &t)){
for(i = ; i <= t; i++){
scanf("%d", &n);
for(j = ; j < n; j++)
scanf("%d", &nNum[j]);
int max = cal(n);
printf("Case %d:\n", i);
printf("%d %d %d\n", max, start + , end + );
if(i != t)
printf("\n");
}
}
return ;
}