package 文件切割;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FilenameFilter;
import java.io.IOException;

public class 文件切割器 {
	public static void main(String[] args) throws IOException {//不要随便运行。。。
		//delet();
		//spiltfilebynum(new File("d:\\dd.txt"), 3);
		//spiltfilebymemory(new File("d:\\dd.txt"),1024*12);
	}
	//输入文件和文件需要被切割的份数 按份数切
	static void spiltfilebynum(File file,int n) throws IOException
	{
		String s=file.getParent();//获取文件路径，用于确定将来被切割的文件放置的路径
		FileInputStream f=new FileInputStream(file);//确定输入流
		
		int count=1;
		long b=file.length();//获取文件长度
		
		int space =(int)b/n;	//开辟数组
		byte arr[]=new byte[space];
		
		int len;
		while((len=f.read(arr))!=-1)
		{
			FileOutputStream fos=new FileOutputStream(new File(s,(count++)+".hahhh"));//确定输出流
			fos.write(arr, 0, len);
			fos.close();
		}
		f.close();
	}
	//告诉我要切多大内存  按内存切
	static void spiltfilebymemory(File file,int n) throws IOException
	{
		int count=1;
		
		String s=file.getParent();
		FileInputStream f=new FileInputStream(file);
		
		byte arr[]=new byte[n];
		
		int len;
		while((len=f.read(arr))!=-1)
		{
			FileOutputStream f2=new FileOutputStream(new File(s,(count++)+".asds")); 
			f2.write(arr, 0, len);
			f2.close();
		}
		f.close();
	}
	static void delet(String s)//用于搞错了删除文件，创了2000多个文件2333
	{
		FilenameFilter f=new FilenameFilter() {
			
			@Override
			public boolean accept(File dir, String name) {
				// TODO Auto-generated method stub
				return name.endsWith(s);
			}
		};
		File file=new File("d:\\");
		File arr[]=file.listFiles();
		for (File file2 : arr) {
			if(file2.isDirectory()) {}
			else
				if(f.accept(file, file2.getName())) 
				{
					file2.delete();
				}
		}
	}
}


 

import java.util.Scanner;
public class Main

{

public static int find[]=new int[100001];

public static void main(String[] args)

{
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext())
	{
		int x=sc.nextInt();
		while(x-->0) {
			int a=sc.nextInt();
			System.out.println(a*2*a-a+1);
		}
	}

}

}

点击打开链接

【问题】：给定一段长度为n英寸的钢条和一个价格表pi（i = 1，2，3…n)求切割方案使得销售受益rn最大。



例如 n = 4

切割方案以及对应的收益为：



【用自顶向下的递归】
//CUT-ROD（p，n）
if  n == 0
     return 0
 q = -无穷
 for i = 1 to  n
     q = max(q,p[i]+CUT-ROD(p,n-i))
 return q;

【用动态规划的思想解决】

动态规划方法仔细安排就切顺序，对每个子问题只求解一次，并将结果保存下来，如果此后自此需要此问题的解，只需查找保存的结果，而 不必重新计算。
动态规划有两种等价的实现方法：

方法一：带备忘的自顶向下法

此方法按自然的递归形式编写过程，但过程会保存每个子问题的解（保存在数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解，是，返回值。
MEMOIZED-CUT-ROD(p,n)
let r[0..n] be a new array
for i = 0 to n
    r[i] = -无穷
return MEMOIZED-CUT-ROD-AUX(p，n，r）

MEMOIZED-CUT-ROD-AUX(p，n，r）
if(r[n]>=0
    return r[n]
if n==0
   q = 0
else q= -wuqiong
   for i = 1 to n
        q = max(q,p[i] + MEMOIZED-CUT-ROD-AUX(p，n-i，r）
r[n] = q
return q

方法二：自底向上法

需要恰当的定义子问题的“规模”，使得任何问题的求解都只依赖于“更小的"子问题的求解。按由小到大的顺序进行求解。
//BOTTOM-UP-CUT-ROD(p,n)
let r[0,1,2...n] be a new array
r[0] = 0
for j = 1 to n
     q = -wuqiong
     for i = 1 to j
         q = max(q,p[i] + r[j-i]
     r[j] = q
return r[n]

扩展版本：不仅保存最优收益值，还保存对应的切割方案
//EXTENDED-BOTTOM-UP-CUT-ROD(p,n)
let r[0,1,2...n] and s[0...n0be a new array
r[0] = 0
for j = 1 to n
     q = -wuqiong
     for i = 1 to j
         if q<p[i]+r[j-i]
             q = p[i]+r[j-i]
             s[j] = i
         r[j] = q
return r and s

【java实现】
package 动态规划;

public class 钢筋分割 {
	//递归方法
	
    public static int cut_rod(int[] p,int n){
        if (n==0){
            return 0;
        }
        int q=-1;
        for (int i=1;i<=n;i++){
            q=Math.max(q,p[i]+cut_rod(p,n-i));
        }
        return q;
    }
    
    //带备忘的自顶向下
    public static int memoizedCutRod(int[] p,int n){
    	int[] r = new int[n+1];
    	for (int i = 0;i < r.length;i++){
    		r[i] = -1;
    	}
    	return MEMOIZED_cut_rod_aux(p,n,r);
    }
    
    public static int MEMOIZED_cut_rod_aux(int[] p,int n,int[]r){
    	if(r[n] >= 0){
    		return r[n];
    	}
    	int q = -1;
    	if(n == 0)  q = 0;
    	else{
    		for(int i = 1;i<=n;i++){
    			q = Math.max(q,p[i]+MEMOIZED_cut_rod_aux(p,n-i,r));
    		}
    	}
    	r[n] = q;
		return q;
    }
    
    //使用自底向上
    public static int bottomUpCutRod(int[] p,int n){
    	int[] r = new int[n+1];
    	for(int i = 0;i<r.length;i++){
    		r[i] = 0;
    	}
    	for(int j = 1;j <= n;j++){
    		int q = -1;
    		for(int i = 1;i<=j;i++){
    			q = Math.max(q, p[i] + r[j-i]);
    		}
    		r[j] = q;
    	}
    	return r[n];
    }
    
    public static void main(String[] args) {
		int[] p = {0,1,5,8,9,10,17,17,20,24,30};
		int n = 4;
		int resultDigui = cut_rod(p,n);
		System.out.println("使用递归方法求得最优收益为"+resultDigui);
		int resultBeiwang = memoizedCutRod(p,n);
		System.out.println("使用带备忘方法求得最优收益为"+resultBeiwang);
		int resultZidiXiangshang = bottomUpCutRod(p,n);
		System.out.println("使用自底向上方法求得最优收益为"+resultZidiXiangshang);
    }

}

运行结果：