soj3104大数三维dp.java

一些ACM题目的解答,主要是soj和poj的

import java.util.*;
import java.math.BigInteger;

public class Main
{
    public static void main(String []args)
    {
        Scanner an = new Scanner(System.in);
        int [][]num = new int[82][82];
        BigInteger [][]dp = new BigInteger[82][82];
        BigInteger []power = new BigInteger[81];
        BigInteger TWO = new BigInteger("2");
        power[1] = TWO;
        power[0] = power[0].ONE;
        int p;
        for(p=2;p<81;p++)
        {
            power[p] = power[p-1].multiply(TWO);
        }
  //      System.out.println(power[80]);
 //       BigInteger minus = new BigInteger("-1");
        while(an.hasNext())
        {
            int n = an.nextInt();
            int m = an.nextInt();
            BigInteger result = new BigInteger("0");
            int i,j,k,h;
            for(i=0;i<82;i++)
            {
                for(j=0;j<82;j++)
                {
                    num[i][j]=0;
                }
            }
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=m;j++)
                {
                    num[i][j]=an.nextInt();
                }
            }
            for(i=1;i<=n;i++)
            {
                for(j=0;j<=m+1;j++)
                {
                     for(k=0;k<=m+1;k++)
                     {
                          dp[j][k]=dp[j][k].ZERO;
                     }
                 }
                for(h=2;h<=m;h++)
                {
                    for(j=1;j<=h;j++)
                    {
                        k=m-h+j;
   //                         if(k<=m)
   //                         {
                                BigInteger t2 = new BigInteger(""+num[i][j-1]);
                                t2 = dp[j-1][k].add(t2.multiply(power[h-1]));
                                BigInteger t1 = new BigInteger(""+num[i][k+1]);
                                t1 = dp[j][k+1].add(t1.multiply(power[h-1]));
                                if(t1.compareTo(t2)<=0)
                                {
                                    dp[j][k] = t2;
                                }
                                else
                                {
                                    dp[j][k] = t1;
                                }
                //                System.out.println(m+"\t"+j+"\t"+k+"\t"+h);
               //                 print(dp[h][j][k]);
    //                        }
                    }
                }
                BigInteger temp =new BigInteger("0");
                for(h=1;h<=m;h++)
                {
                    BigInteger rr = new BigInteger(""+num[i][h]);
                    dp[h][h] = dp[h][h].add(rr.multiply(power[m]));
                    if(temp.compareTo(dp[h][h])<0)
                        temp=dp[h][h];
      //              print(temp);
                }
                result = result.add(temp);
            }
            System.out.println(result);
        }
    }        
}