小蓝在一个 nn 行 mm 列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第 11 行第 11 列。
小蓝可以在方格图上走动，走动时，如果当前在第 rr 行第 cc 列，他不能走到行号比 rr 小的行，也不能走到列号比 cc 小的列。同时，他一步走的直线距离不超过 33。
例如，如果当前小蓝在第 33 行第 55 列，他下一步可以走到第 33 行第 66 列、第 33 行第 77 列、第 33 行第 88 列、第 44 行第 55 列、第 44 行第 66 列、第 44 行第 77 列、第 55 行第 55 列、第 55 行第 66 列、第 66 行第 55 列之一。
小蓝最终要走到第 nn 行第 mm 列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第 11 行第 11 列走到第 nn 行第 mm 列后，总的权值和最大。请问最大是多少？
输入的第一行包含两个整数 n,mn,m，表示图的大小。
接下来 nn 行，每行 mm 个整数，表示方格图中每个点的权值。
其中，1≤n≤100，−104≤权值≤1041≤n≤100，−104≤权值≤104。
输出一个整数，表示最大权值和。
示例 1
输入
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
输出
15
实现：
import java.util.Scanner;
public class jump {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
int[][] arr=new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
arr[i][j]=scan.nextInt();
}
}
scan.close();
int[][] b=new int[n][m];
b[0][0]=arr[0][0];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
int c=3;
while(c>0) {
if(i-c>=0) {
b[i][j]=Math.max(b[i][j], b[i-c][j]+arr[i][j]);
}
if(j-c>=0) {
b[i][j]=Math.max(b[i][j], b[i][j-c]+arr[i][j]);
}
c--;
}
}
}
System.out.println(b[n-1][m-1]);
}
}
动态规划求最长子序列
L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 11 至 55 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
其中有 ，两个字符串的长度均不超过 10001000。
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
示例
输入
LanQiaoBei
LanTaiXiaoQiao
输出
2
import java.util.*;
public class lantai {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
String str1=scan.nextLine();
String str2=scan.nextLine();
scan.close();
int[] flag1=new int[str1.length()];
int[] flag2=new int[str2.length()];
int c=0;
int m=0,n=0;
for(int i=0;i<str1.length();i++) {
if(str1.charAt(i)>='A'&&str1.charAt(i)<='Z') {
flag1[c]=i;
c++;
m++;
}
}
flag1[c]=str1.length();
c=0;
for(int i=0;i<str2.length();i++) {
if(str2.charAt(i)>='A'&&str2.charAt(i)<='Z') {
flag2[c]=i;
c++;
n++;
}
}
flag2[c]=str2.length();
int[][] dp=new int[m+1][n+1];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
// System.out.println(str1.substring(flag1[i], flag1[i+1])+" "+str2.substring(flag2[j], flag2[j+1]));
if(str1.substring(flag1[i], flag1[i+1]).equals(str2.substring(flag2[j], flag2[j+1]))) {
dp[i+1][j+1]=Math.max(dp[i+1][j+1], dp[i][j]+1);
}else{
dp[i+1][j+1]=Math.max(dp[i][j+1], dp[i+1][j]);
}
}
}
System.out.println(dp[m][n]);
}
}
上述有两例发生段错误，
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
String str1=scan.nextLine();
String str2=scan.nextLine();
scan.close();
int[] flag1=new int[str1.length()+1];
int[] flag2=new int[str2.length()+1];
int c=0;
int m=0,n=0;
for(int i=0;i<str1.length();i++) {
if(str1.charAt(i)>='A'&&str1.charAt(i)<='Z') {
flag1[c]=i;
c++;
m++;
}
}
flag1[c]=str1.length();
c=0;
for(int i=0;i<str2.length();i++) {
if(str2.charAt(i)>='A'&&str2.charAt(i)<='Z') {
flag2[c]=i;
c++;
n++;
}
}
flag2[c]=str2.length();
int[][] dp=new int[m+1][n+1];
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
// System.out.println(str1.substring(flag1[i-1], flag1[i])+" "+str2.substring(flag2[j-1], flag2[j]));
if(str1.substring(flag1[i-1], flag1[i]).equals(str2.substring(flag2[j-1], flag2[j]))) {
dp[i][j]=Math.max(dp[i][j], dp[i-1][j-1]+1);
}else{
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
System.out.println(dp[m][n]);
}
}
包子凑数：
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 NN 种蒸笼，其中第 ii 种蒸笼恰好能放 AiAi 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买 XX 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 XX 个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
第一行包含一个整数 NN (1≤N≤1001≤N≤100)。
以下 N 行每行包含一个整数 AiAi (1≤Ai≤1001≤Ai≤100)。
一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。
示例 1
输入
2
4
5
输出
6
样例说明
凑不出的数目包括：1, 2, 3, 6, 7, 11。
示例 2
输入
2
4
6
输出
INF
样例说明
所有奇数都凑不出来，所以有无限多个
import java.util.*;
public class baozicoushu {
public static int gcd(int a,int b) {
if(b==0) {
return a;
}else {
return gcd(b,a%b);
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int[] a=new int[n+1];
int s;
for(int i=1;i<=n;i++) {
a[i]=scan.nextInt();
}
scan.close();
s=a[1];
for(int i=1;i<=n;i++) {
s=gcd(s,a[i]); //求得最大公约数（所输入每一笼包子数的最大公约数）
}
if(s!=1) { //这些数中包含最大公约数，不互质，例如3,6,9这些数不能组成的数为无穷
System.out.println("INF");
}else{
boolean[] f=new boolean[10001];
f[0]=true;
for(int i=1;i<=n;i++) {
for(int j=0;j<10001;j++) { //标记数组，寻找不能凑成的数字
if(f[j]&&(j+a[i])<10001) {
f[j+a[i]]=true;
}
}
}
int sum=0;
for(int i=1;i<10001;i++) {
if(!f[i]) {
sum++;
}
}
System.out.println(sum);
}
}
}
01背包问题
回溯： 
import java.util.*;
public class ZeroAndOne {
public static void main(String[] args) {
int[][] dp=new int[5][9];
int[] w= {0,2,3,4,5}; //物品对应的容量
int[] v= {0,3,4,5,8}; //物品对应的价值
for(int i=1;i<5;i++) {
for(int j=1;j<9;j++) { //j表示背包容量
if(w[i]>j) {
dp[i][j]=dp[i-1][j];
}else {
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
} //不偷第i-1个物品 偷
}
}
System.out.print(dp[4][8]);
}
}
背包与魔法
小蓝面前有 NN 件物品, 其中第 ii 件重量是 WiWi, 价值是 ViVi 。她还有一个背包, 最大承重是 MM 。
小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?
特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 KK, 同时价值秝倍。(当然小蓝也可以不使用魔法)
第一行包含 3 个整数 N、MN、M 和 KK 。
以下 NN 行, 每行两个整数 WiWi 和 ViVi 。
一个整数代表答案。
3 10 3
5 10
4 9
3 8
26
选择第二件和第三件物品, 同时对第二件物品使用魔法。
对于 30%30% 的数据, 1≤N,M,K≤1001≤N,M,K≤100.
对于 100%100% 的数据, 1≤N≤2000,1≤M,K≤10000,0≤Wi,Vi≤100001≤N≤2000,1≤M,K≤10000,0≤Wi,Vi≤10000.
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 3s | 256M |
| Python3 | 5s | 256M |
状态转移方程：
若不使用魔法，也就是j=0的时候的情况，跟01背包的模板一样，
dp[j][0] = Math.max(dp[j][0],dp[j-w[i]][0]+v[i])
若使用魔法，（要保证j的大小符合条件）
有两种情况，这次的物品使用魔法或者之前其中的一个物品使用魔法
1.若这次物品使用魔法，即Math.max(dp[j-w[i]-k][0]+2*v[i]
2.若之前其中的一个物品使用魔法，即dp[j-w[i]][1]+v[i]
合起来就是dp[j][1] = Math.max(dp[j][1],Math.max(dp[j-w[i]-k][0]+2*v[i],dp[j-w[i]][1]+v[i]));
import java.util.*;
public class PacageAndMagin {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int k = scan.nextInt();
int[] w = new int[n+1];
int[] v = new int[n+1];
w[0]=0;
v[0]=0;
for(int i=1;i<=n;i++) {
w[i]=scan.nextInt();
v[i]=scan.nextInt();
}
scan.close();
// int[][] dp=new int[n+1][m+1];
// for(int i=1;i<n+1;i++) {
// for(int j=1;j<m+1;j++) {
// if(j<w[i]) {
// dp[i][j]=dp[i-1][j];
// }else {
// System.out.println(i+" "+j);
// dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
// System.out.println(i+" "+j);
// }
// }
// }
int[][] dp=new int[m+1][2];
for(int i=1;i<n+1;i++) {
for(int j=m;j>=w[i];j--) {
if(j>=k+w[i]) {//使用药水或者之前使用药水
dp[j][0]=Math.max(dp[j][0],dp[j-w[i]][0]+v[i] );
//没有使用药水的最优组合 不装这个物品当前容量的最优组合，装下当前物品的最优组合
dp[j][1]=Math.max(dp[j][1], Math.max(dp[j-w[i]-k][0]+2*v[i], dp[j-w[i]][1]+v[i]));
// 之前使用药水但这次不装入物品的最优组合 这次使用药水并装入这个物品的最优组合，这次不用使药水但之前使用药水的最优组合
}else {
dp[j][0]=Math.max(dp[j][0], dp[j-w[i]][0]+v[i]);
}
}
}
System.out.println(Math.max(dp[m][0], dp[m][1]));
}
}
我已经构建了一些serverspec代码来在多个主机上运行一组测试。问题是当任何测试失败时，测试会在当前主机停止。即使测试失败，我也希望它继续在所有主机上运行。Rakefile:namespace:specdotask:all=>hosts.map{|h|'spec:'+h.split('.')[0]}hosts.eachdo|host|begindesc"Runserverspecto#{host}"RSpec::Core::RakeTask.new(host)do|t|ENV['TARGET_HOST']=hostt.pattern="spec/cfengine3/*_spec.r
我想学习一些关于Continuation的知识，使用callcc方法从一些文章中键入几个示例，但我遇到了错误:NoMethodError:undefinedmethod`callcc'formain:Objectfrom(pry):2:in`'没有文章提到包含延续库。那么如何解决这个问题呢？谢谢编辑:ruby1.9.2p290(2011-07-09修订版32553)[x86_64-linux] 最佳答案 您需要要求“继续”。require'continuation' 关于ruby-继续，
运行bundleinstall后出现此错误:Gem::Package::FormatError:nometadatafoundin/Users/jeanosorio/.rvm/gems/ruby-1.9.3-p286/cache/libv8-3.11.8.13-x86_64-darwin-12.gemAnerroroccurredwhileinstallinglibv8(3.11.8.13),andBundlercannotcontinue.Makesurethat`geminstalllibv8-v'3.11.8.13'`succeedsbeforebundling.我试试gemin
有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.
我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO
首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟
我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]
如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？ 最佳答案 我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail
如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法，给定上面的散列，执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道，但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210
我有一个ruby程序，我想接受用户创建的方法，并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗？谢谢。编辑:我以不同的方式让它工作，但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method