E81086713E446D36F62B2AA2A3502B5EB155

Java杂家

杂七杂八。。。一家之言

BlogJava 首页 新随笔 联系 聚合 管理
  141 Posts :: 1 Stories :: 174 Comments :: 0 Trackbacks
年过的差不多了,今天偶尔兴起上HOJ上翻几道DP练手的题来。。。,顺便把代码贴下留念 
1.数塔
/**
 * 
 
*/
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;

    }
}
2.Super Jumping!Jumping!Jumping!
简单的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;
    }

}
3.免费馅饼
 这道题跟数塔其实很像的,可以看作是它的变型。题目说明数据量可能很大,怕超时,故用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], 0sizeof(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], 
0sizeof(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;
}
posted on 2011-02-06 21:13 DoubleH 阅读(2000) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: