485表上，副申请人的application type是哪个？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

485表上，副申请人的application type是哪个？

485表上，副申请人的application type是哪个？# Immigration - 落地生根

l*g2012-12-10 08:12

1 楼

请教一道DP问题，大概是这样的：
有一个长为L的木料需要割开，切的位置在一个数组里A[0...N]，从一个地方切开的
cost是当前所切木料的长度。按不同的顺序切割，得到的total cost是不一样的，问怎
么切cost最 小。
我对题意的理解是，比如一个木料现在10米长，然后切的位置是2米处，4米处和7米处
（就是说arr A里A[0]是2，A[1]是4， A[2]是7）。那么比如先切2米，那么得到cost是
10（因为现在木料长度为10），然后切4米处，那么cost变成10 + 8(因为8是现在切的
时候木料的长度)。然后切7米处，cost变成10 + 8 + 6。那么这种切法总共的cost是24。
这题DP应该怎么写？递推关系是什么？谢谢！

j*u2012-12-10 08:12

2 楼

要交95/年费吗？

F*12012-12-10 08:12

3 楼

副申请人是选择
a.
An immigrant petition giving me an immedicately available immigrant visa
number that has been approved.
还是
b.
My spouse or parent applied for adjustment of status or was granted lawful
permanent residence in an immigrant visa category that allows derivative
status for spouses and children.
多谢！！！

d*i2012-12-10 08:12

4 楼

代码已贴。
public static int rodCutting(int[] price, int RodLength) {
int dp[] = new int[RodLength + 1];
for (int i = 1; i <= RodLength; i++) {
for (int j = 0; j < price.length; j++) {
if (j < i) {
dp[i] = Math.max(dp[i], dp[j] + price[i - 1 - j]);
}
}
}
return dp[RodLength];
}

j*u2012-12-10 08:12

5 楼

没人知道吗？

F*12012-12-10 08:12

6 楼

是b么？确认一下。

【在 F******1 的大作中提到】

: 副申请人是选择
: a.
: An immigrant petition giving me an immedicately available immigrant visa
: number that has been approved.
: 还是
: b.
: My spouse or parent applied for adjustment of status or was granted lawful
: permanent residence in an immigrant visa category that allows derivative
: status for spouses and children.
: 多谢！！！

w*32012-12-10 08:12

7 楼

i表示计算的长度，j表示最后一切的位置，0放入index0，L放入最后一个index为编程
方便一些。比如说i=2 j=3的dp[2][3]表示楼主例子中2~7这一段的最小cost
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 2; i < a.size(); i++) {
dp[2][i] = a.get(i) - a.get(i-2);
}
for (int i = 3; i < a.size(); i++) {
for (int j = i; j < a.size(); j++) {
dp[i][j] = (a.get(j) - a.get(j-i)) + Math.min(dp[i-1][j], dp
[i-1][j-1]);
}
}
return dp[a.size()-1][a.size()-1];
}

m*r2012-12-10 08:12

8 楼

交

i*t2012-12-10 08:12

9 楼

我选的b

i*52012-12-10 08:12

10 楼

你是今儿面的A吗？

G*82012-12-10 08:12

11 楼

交

w*s2012-12-10 08:12

12 楼

l*g2012-12-10 08:12

13 楼

这个代码对这道题不work。。。对cut rob那道题应该work。。。

【在 d********i 的大作中提到】

: 代码已贴。
: public static int rodCutting(int[] price, int RodLength) {
: int dp[] = new int[RodLength + 1];
: for (int i = 1; i <= RodLength; i++) {
: for (int j = 0; j < price.length; j++) {
: if (j < i) {
: dp[i] = Math.max(dp[i], dp[j] + price[i - 1 - j]);
: }
: }
: }

d*g2012-12-10 08:12

14 楼

交

L*L2012-12-10 08:12

15 楼

我填了b

l*g2012-12-10 08:12

16 楼

可能是我题意没讲清。。。我对题目的理解是：
比如还是之前的例子，但是如果第一下切4那个位置的话，首先cost = 10, 然后把木料
分成了4和6两段。然后切2那个位置，这个时候cost = 10 + 4，因为2这个位置现在位
于长度是4的这一半，然后第三下切7那里，cost = 10 + 4 + 6。那么这样切的话总
cost就是20。你的代码似乎返回的是21。。。

【在 w****3 的大作中提到】

: i表示计算的长度，j表示最后一切的位置，0放入index0，L放入最后一个index为编程
: 方便一些。比如说i=2 j=3的dp[2][3]表示楼主例子中2~7这一段的最小cost
: public int cutWood(int [] input, int L) {
: ArrayList a = new ArrayList();
: a.add(0);
: for (int i = 0; i < input.length; i++)
: a.add(input[i]);
: a.add(L);
: int [][] dp = new int [a.size()][a.size()];
: //initalize cut to 2 pieces

w*r2012-12-10 08:12

17 楼

这卡好吗？有啥好处？

F*12012-12-10 08:12

18 楼

这下安心了。。多谢。。
还好检查了一下，发现竟然两个以前都选了 a...

l*g2012-12-10 08:12

19 楼

不是。。。还在看面经的节奏。。。

【在 i********5 的大作中提到】

: 你是今儿面的A吗？

i*r2012-12-10 08:12

20 楼

能拿retention offer吗？

a*m2012-12-10 08:12

21 楼

不错的题目。

24。

【在 l**********g 的大作中提到】

: 请教一道DP问题，大概是这样的：
: 有一个长为L的木料需要割开，切的位置在一个数组里A[0...N]，从一个地方切开的
: cost是当前所切木料的长度。按不同的顺序切割，得到的total cost是不一样的，问怎
: 么切cost最 小。
: 我对题意的理解是，比如一个木料现在10米长，然后切的位置是2米处，4米处和7米处
: （就是说arr A里A[0]是2，A[1]是4， A[2]是7）。那么比如先切2米，那么得到cost是
: 10（因为现在木料长度为10），然后切4米处，那么cost变成10 + 8(因为8是现在切的
: 时候木料的长度)。然后切7米处，cost变成10 + 8 + 6。那么这种切法总共的cost是24。
: 这题DP应该怎么写？递推关系是什么？谢谢！

j*32012-12-10 08:12

22 楼

是不是CSP交年费唯一的好处就是能转点到UA？谢谢值得年费吗？
谢谢

E*e2012-12-10 08:12

23 楼

每次切中间？greedy?

j*u2012-12-10 08:12

24 楼

是不是CSP交年费唯一的好处就是能转点到UA？谢谢值得年费吗？

i*52012-12-10 08:12

25 楼

今天亚麻考了这道！

不是。。。还在看面经的节奏。。。

【在 l**********g 的大作中提到】

: 不是。。。还在看面经的节奏。。。

y*i2012-12-10 08:12

26 楼

basically yes, but not limited to UA only, for example, Hyatt points may
also give you much better value
keep at least one CSP or Ink Plus/Bold card between you and your spouse
well worth the annual fee for the purpose of transferring points alone

【在 j**u 的大作中提到】

: 是不是CSP交年费唯一的好处就是能转点到UA？谢谢值得年费吗？

l*g2012-12-10 08:12

27 楼

这么难。。。

【在 i********5 的大作中提到】

: 今天亚麻考了这道！
:
: 不是。。。还在看面经的节奏。。。

q*n2012-12-10 08:12

28 楼

首先，得到每一块木头的长度，例如，楼主的例子：
L[0] = 2, L[1] = 2, L[2] = 3, L[3] = 3
然后，定义DP[i][j]为从第i块木头的左边开始切，切j块木头的最优解。
DP[i][1] = 0
DP[i][2] = L[i] + L[i+1]
DP[i][3] = L[i] + L[i+1] + L[i+2] + min (DP[i][1]+DP[i+1][2],DP[i][2]+DP[i+2
][1])
以此类推就可以了

f*n2012-12-10 08:12

29 楼

mark

p*n2012-12-10 08:12

30 楼

M[i][j] 记录从木头的第 i 段到第j段之间的subsolution。
细节：
首先对角线上的元素(从左上到右下)都初始化0, 因为 i 到i 段不用cut，所以cost 为
0
从i,j 之间，假设我们只能cut 两个大段，左大段和右大段，则总共有 i-j-1种cut
方法(i j之间每个可能cut的地方都试一次)
M[i][j] ＝ A[j] - A[i] (注释：i-j之间的木头长度) +
min(M[i][i] + M[i+1][j], M[i][i+1] + M[i+2][j]), ... M[i][j-1] + M[j
][j]);
这个M矩阵，我们从下往上计算，每层从右往左计算，只有矩阵的右上一半被计算，
左下方不管。

24。

【在 l**********g 的大作中提到】

l*g2012-12-10 08:12

31 楼

看起来应该work，不过我按照你的思路写了一下代码，跑我给的这个例子给出的答案是
19。。。但最小的cost应该是20？
代码如下，
public static void main(String[] args) {
int[] input = {2, 4, 7};
int L = 10;
System.out.println(cutWood(input, L));
}

public static int cutWood(int[] input, int L) {
int len = input.length;
int[] A = new int[len + 2];
A[0] = 0;
for (int i = 0; i < len; i++) {
A[i + 1] = input[i];
}
A[len + 1] = L;
int[][] M = new int[len + 2][len + 2];
for (int i = len; i >= 0; i--) {
for (int j = i + 1; j < len + 2; j++) {
M[i][j] = A[j] - A[i];
int min = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
min = Math.min(M[i][k] + M[k + 1][j], min);
}
M[i][j] += min;
}
}
return M[0][len + 1];
}
还是说我写的这个和你的思路并不一样？。。。

[j

【在 p********n 的大作中提到】

: M[i][j] 记录从木头的第 i 段到第j段之间的subsolution。
: 细节：
: 首先对角线上的元素(从左上到右下)都初始化0, 因为 i 到i 段不用cut，所以cost 为
: 0
: 从i,j 之间，假设我们只能cut 两个大段，左大段和右大段，则总共有 i-j-1种cut
: 方法(i j之间每个可能cut的地方都试一次)
: M[i][j] ＝ A[j] - A[i] (注释：i-j之间的木头长度) +
: min(M[i][i] + M[i+1][j], M[i][i+1] + M[i+2][j]), ... M[i][j-1] + M[j
: ][j]);
: 这个M矩阵，我们从下往上计算，每层从右往左计算，只有矩阵的右上一半被计算，

l*g2012-12-10 08:12

32 楼

求大牛解答。。。

z*t2012-12-10 08:12

33 楼

定义:
val[i]：数组A里面下标为i-1的数值，val[0]=0而val[N+1]=L
f（i,j)代表val[i]到val[j]木头段切割完的最小花销
递推公式是：
f(i,j) = min [(f(i,k) + f(k,j)) where i < k < j] + val(j) - val(i);
如果i>=j,递推无效
如果i+1==j,f返回0，因为不需要在val[i]和val[j]之间做切割
其他的就很简单了，只需要一个二维数组存中间结果，最后需要计算的是f(0,N+1)。我
就不贴代码了。

l*g2012-12-10 08:12

34 楼

感觉思路和我上面写的代码一样。。。可以麻烦看看我写的代码哪儿不对吗？谢谢！

【在 z******t 的大作中提到】

: 定义:
: val[i]：数组A里面下标为i-1的数值，val[0]=0而val[N+1]=L
: f（i,j)代表val[i]到val[j]木头段切割完的最小花销
: 递推公式是：
: f(i,j) = min [(f(i,k) + f(k,j)) where i < k < j] + val(j) - val(i);
: 如果i>=j,递推无效
: 如果i+1==j,f返回0，因为不需要在val[i]和val[j]之间做切割
: 其他的就很简单了，只需要一个二维数组存中间结果，最后需要计算的是f(0,N+1)。我
: 就不贴代码了。

o*g2012-12-10 08:12

35 楼

我就用最笨的方法。
一段木头，每个地方都切一下。每次切的时候都有左右两段。每次切的cost就是左边那
段的cost+右边的cost+整根木头的长度。所有地方都试过，然后找最小值，就是这段木
头的cost最小值了。
公式：
cost[A] = min{cost[0到i]+cost[i到n-1]+L}
好绕，下面是代码，楼主的case算出来是20
public class Solution
{
public int cutRod(int[] A, int L)
{
int result = Integer.MAX_VALUE;
int n = A.length;
if (n == 0)
{
return 0;
}
for (int i = 0; i < n; i++)
{
int[] left = new int[i];
for (int j = 0; j < i; j++)
{
left[j] = A[j];
}
int[] right = new int[n - i - 1];
for (int j = i + 1; j < n; j++)
{
right[j - i - 1] = A[j];
}
int minLeft = cutRod(left, A[i]);
int minRight = cutRod(right, L - A[i]);
result = Math.min(result, minLeft + minRight + L);
}
return result;
}
public static void main(String[] argv)
{
Solution solution = new Solution();
int[] input = new int[] { 2, 4, 7 };
System.out.println(solution.cutRod(input, 10));
}
}

H*r2012-12-10 08:12

36 楼

The first DP problem in CLRS?

x*62012-12-10 08:12

37 楼

mark

w*32012-12-10 08:12

38 楼

是我想错了，dp的时候再加一层循环，最后return 20.复杂度似乎是n^3
其实和楼上几位的想法是一样的，先将切每段短的木料的cost算出来，每次新加一段的
时候，尝试第一刀切在这段之前的所有位置，切成两段以后的cost都已经知道了，所以
在这k个切法里找到最小的存下来即可。
public int cutWood(int [] input, int L) {
ArrayList a = new ArrayList();
a.add(0);
for (int i = 0; i < input.length; i++)
a.add(input[i]);
a.add(L);
int [][] dp = new int [a.size()][a.size()];
//initalize cut to 2 pieces
for (int i = 1; i < a.size(); i++) {
dp[1][i] = 0;
}
for (int i = 2; i < a.size(); i++) {
for (int j = i; j < a.size(); j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int k = j - i + 1; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], a.get(j) - a.get(j-i) + dp
[k - j + i][k] + dp[j - k][j]);
}
}
}
return dp[a.size()-1][a.size()-1];
}

【在 l**********g 的大作中提到】

: 可能是我题意没讲清。。。我对题目的理解是：
: 比如还是之前的例子，但是如果第一下切4那个位置的话，首先cost = 10, 然后把木料
: 分成了4和6两段。然后切2那个位置，这个时候cost = 10 + 4，因为2这个位置现在位
: 于长度是4的这一半，然后第三下切7那里，cost = 10 + 4 + 6。那么这样切的话总
: cost就是20。你的代码似乎返回的是21。。。

s*r2012-12-10 08:12

39 楼

这个问题我从去年就不会，一直到现在

l*n2012-12-10 08:12

40 楼

弱问dp是什么。。。

k*s2012-12-10 08:12

41 楼

抛迭代砖
def min_cost(self, A, L):
memory = [[0 for _ in range(len(A) + 2)] for _ in range(len(A) + 2)]

cuts = list(A)
cuts.append(0)
cuts.append(L)
cuts.sort()

for length in range(2, len(cuts)):
for start in range(0, len(cuts) - length):
min_cost = float('Inf')
fix_cost = (cuts[start + length] - cuts[start])
for i in range(start + 1, start + length):
min_cost = min(min_cost, memory[start][i] +
memory[i][start + length] + fix_cost)
memory[start][start + length] = min_cost

return memory[0][len(A) + 1]

k*s2012-12-10 08:12

42 楼

抛低轨砖
def __min_cost_rec(self, cuts, start, end, memory):
if memory[start][end] is None:
fix_cost = cuts[end] - cuts[start]
min_cost = float('Inf')
for i in range(start + 1, end):
min_cost = min(min_cost,
self.__min_cost_rec(cuts, start, i, memory) +
self.__min_cost_rec(cuts, i, end, memory) +
fix_cost)
memory[start][end] = min_cost;
return memory[start][end];

def min_cost_rec(self, A, L):
memory = [[None for _ in range(len(A) + 2)] for _ in range(len(A) +
2)]
for i in range(0, len(memory) - 1):
memory[i][i + 1] = 0

cuts = list(A)
cuts.append(0)
cuts.append(L)
cuts.sort()

return self.__min_cost_rec(cuts, 0, len(cuts) - 1, memory)

f*82012-12-10 08:12

43 楼

cut[][] = new int[][]{-1}; // cache the known best cut
start[]={0,2,4,7};
end[]={2,4,7,10};
getBestCut(from, to){
if (cut[from][to] != -1) {
return cut[from][to];
}
if (from == to)
return 0;
min = getBestCut(from + 1, to); // getBestCut(from, from) == 0.
for (i = from + 1; i < to; ++i) {
tryCut = getBestCut(from, i) + getBestCut(i + 1, to);
if (tryCut < min) min = tryCut;
}
min += end[to] - start[from];
cut[from][to] = min;
return min;
}
本人刚刚COMPUTER ENGINEERING毕业，正在找湾区工作，求内推：f****[email protected]，谢
谢！

b*r2012-12-10 08:12

44 楼

this is pretty close, though you don't need to recursive call and can use a
table to store value.

【在 o***g 的大作中提到】

: 我就用最笨的方法。
: 一段木头，每个地方都切一下。每次切的时候都有左右两段。每次切的cost就是左边那
: 段的cost+右边的cost+整根木头的长度。所有地方都试过，然后找最小值，就是这段木
: 头的cost最小值了。
: 公式：
: cost[A] = min{cost[0到i]+cost[i到n-1]+L}
: 好绕，下面是代码，楼主的case算出来是20
: public class Solution
: {
: public int cutRod(int[] A, int L)