首页 > 代码库 > 【Java】【滚动数组】【动态规划】UVA - 11137 - Ingenuous Cubrency
【Java】【滚动数组】【动态规划】UVA - 11137 - Ingenuous Cubrency
滚动数组优化自己画一下就明白了。
http://blog.csdn.net/u014800748/article/details/45849217
解题思路：本题利用递推关系解决。建立一个多段图，定义状态d(i,j)表示“使用不超过i的整数的立方，累加和为j”的方案数。那么根据加法原理，如果没有选择数字i的立方和就得到了j，那么方案数就是d(i-1,j)；如果选择了数字i的立方和才得到了j，那么方案数是d(i,j-i^3)。即：
d(i,j)=d(i-1,j)+d(i,j-i^3);
这个递推式还可以降低维度，利用滚动数组计算。由递推式可知，i,j都需要从小到大计算，而更新i的时候，d(j)保存的是第i-1次计算时的结果，此时可以用d(j)更新d(j+i^3)的状态。即只需要d(j+i^3)+=d(j)即可完成上述方程的计算。
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
static long[] f=new long[10010];
public static void main(String[] argc){
Scanner sc = new Scanner (new BufferedInputStream(System.in));
f[0]=1l;
for(int i=1;i<=21;++i){
for(int j=0;j<=10000;++j){
if(j+i*i*i<=10000){
f[j+i*i*i]+=f[j];
}
}
}
while(sc.hasNext()){
int n=sc.nextInt();
System.out.println(f[n]);
}
sc.close();
}
}
【Java】【滚动数组】【动态规划】UVA - 11137 - Ingenuous Cubrency
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。