年過的差不多了，今天偶爾興起上HOJ上翻幾道DP練手的題來。。。，順便把代碼貼下留念
/**
*
*/
package hduacm;
import java.util.Scanner;
/**
* http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1001&cid=9066&hide=0
*
* @author yovn
*
*/
public class P1001 {
/**
*
* @param args
*/
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int nline = cin.nextInt();
for (int i = 0; i < nline; i++) {
int nn = cin.nextInt();
int tn = (nn * (nn + 1)) / 2;
int arr[] = new int[tn];
int delta = 0;
for (int k = 0; k < nn; k++) {
for (int j = 0; j <= k; j++) {
arr[delta + j] = cin.nextInt();
}
delta += k + 1;
}
int max = solve(arr, tn, nn);
System.out.println(max);
}
}
private static int solve(int[] arr, int tn, int nn) {
int delta = 0;
int max[] = new int[tn];
max[0] = arr[0];
int maxt = max[0];
delta = 1;
for (int k = 1; k < nn; k++) {
// 計算第(k+1)行
for (int j = 0; j <= k; j++) {
if (j == 0) {
max[delta + j] = max[delta - k] + arr[delta + j];
} else if (j == k) {
max[delta + j] = max[delta - 1] + arr[delta + j];
} else {
if (max[delta - k + j] > max[delta - k + j - 1]) {
max[delta + j] = max[delta - k + j] + arr[delta + j];
} else {
max[delta + j] = max[delta - k + j - 1]
+ arr[delta + j];
}
}
if (k == nn - 1 && max[delta + j] > maxt) {
maxt = max[delta + j];
}
}
delta += k + 1;
}
return maxt;
}
}
簡單的DP題
/**
*
*/
package hduacm;
import java.util.Scanner;
/**
* http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1002&cid=9066&hide=0
* @author yovn
*
*/
public class P1002 {
/**
* @param args
*/
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int nn=cin.nextInt();
while(nn>0){
int arr[]=new int[nn];
for(int i=0;i<nn;i++){
arr[i]=cin.nextInt();
}
int max=solve(arr,nn);
System.out.println(max);
nn=cin.nextInt();
}
}
private static int solve(int[] arr, int nn) {
int max[]=new int[nn];
System.arraycopy(arr, 0, max, 0, nn);
int maxt=max[0];
for(int j=1;j<nn;j++){
for(int k=j-1;k>=0;k--){
if(arr[j]>arr[k]){
if(arr[j]+max[k]>max[j]){
max[j]=arr[j]+max[k];
}
}
}
if(max[j]>maxt){
maxt=max[j];
}
}
return maxt;
}
}
這道題跟數塔其實很像的，可以看作是它的變型。題目說明數據量可能很大，怕超時，故用C++實現之。
#include <cstdio>
#include <cstdlib>
#include <memory.h>
int infos[100000][11]={{0}};
int main(void) {
int tn;
int maxt = 0;
int a, b;
while (scanf("%d", &tn) != EOF) {
if (tn == 0)
break;
memset(&infos[0][0], 0, sizeof(infos));
for (int i = 0; i < tn; i++) {
scanf("%d%d", &a, &b);
if (b > maxt) {
maxt = b;
}
infos[b][a] += 1;
}
int** max = new int*[maxt + 1];
for (int i = 0; i <= maxt; i++) {
max[i] = new int[11];
memset(max[i], 0, sizeof(int) * 11);
}
int maxnn = 0;
for (int i = 1; i <= maxt; i++) {
for (int j = 0; j <= 10; j++) {
if(i==1 && (j<4 || j>6))continue;//從5開始
if (j == 0) {
if (max[i - 1][j] > max[i - 1][j + 1]) {
max[i][j] = max[i - 1][j] + infos[i][j];
} else {
max[i][j] = max[i - 1][j + 1] + infos[i][j];
}
} else if (j == 10) {
if (max[i - 1][j] > max[i - 1][j - 1]) {
max[i][j] = max[i - 1][j] + infos[i][j];
} else {
max[i][j] = max[i - 1][j - 1] + infos[i][j];
}
} else {
if (max[i - 1][j] > max[i - 1][j - 1]) {
if (max[i - 1][j] > max[i - 1][j + 1]) {
max[i][j] = max[i - 1][j] + infos[i][j];
} else {
max[i][j] = max[i - 1][j + 1] + infos[i][j];
}
} else {
if (max[i - 1][j - 1] > max[i - 1][j + 1]) {
max[i][j] = max[i - 1][j - 1] + infos[i][j];
} else {
max[i][j] = max[i - 1][j + 1] + infos[i][j];
}
}
}
if (i == maxt && max[i][j] > maxnn) {
maxnn = max[i][j];
}
}
}
for (int i = 0; i <= maxt; i++) {
delete[] max[i];
max[i] = NULL;
}
delete[] max;
printf("%d\n", maxnn);
}
return 0;
}