s******n
发帖数: 3946 | 1 你再看看？第一年应该是60，如果买机器加上去也是1060，怎么会出来260？
int MinCost(int years)
{
if(years==0)
return 0;
if (years==1) {
// 换,修
return min(1000-800,60)
} else if (years==2) {
// 换+MinCost(1)，修修，修换
return min(100-800+MinCost(1), 60+80, 60+(1000-600));
} else if (years=3) {
// 换+MinCost(2)，修修修，修修换，修换+MinCost(1)
return min(1000-800+MinCost(2), 60+80+120, 60+80+(1000-500), 60+(1000
-600)+MinCost(1));
} else {
// 修修换+MinCost(years-3)，修... 阅读全帖 |
|
p*****2
发帖数: 21240 | 2 int MinCost(int years)
{
if(years==0)
return 0;
int c1,c2,c3 = MAX_INT;
c1=1000-800+60+MinCost(years-1);
if(years>=2)
c2=1000-600+60+80+MinCost(years-2);
if(years>=3)
c3=1000-500+60+80+120+MinCost(years-3);
return min(c1,c2,c3);
}
用hashtable可以cache吧。 |
|
发帖数: 1 | 3 二维比较难想，可以先想想一维的情况。这题也可能和二分图有关。我下班后试试。
我擦，匈牙利算法早忘光光了，只记得dfs, 囧。。。
class Location {
Location(int x, int y) {
this.x = x;
this.y = y;
}
public int hashCode() {
return x | y;
}
public boolean equals(Object obj) {
if (obj == null) return false;
else {
if (obj instanceof Location) {
Location l = (Location)obj;
return l.x == x && l.y == y;
} else {
return false;
... 阅读全帖 |
|
z******w
发帖数: 36 | 4 用dp实现了一下，内存可以用滚动数组代替变成O(datarange)的空间复杂度，时间复杂
度是O(length*datarange)
public class MinCost {
public int getMin1(int[] input) {
if (input.length <= 1) return 0;
int max = 0;
for (int i = 0; i < input.length; i ++) {
max = Math.max(max, input[i]);
}
int[][] dp = new int[input.length][max+1];
for (int j = 0; j <= max; j ++) {
dp[0][j] = Math.max(0, input[0]-j);
}
for (int i = 1; i < dp.length; i ++) {
... 阅读全帖 |
|
S**I
发帖数: 15689 | 5 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Aug 30 00:32:06 2011, 美东) 提到:
Given an array A of positive integers. Convert it to a sorted array with
minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Aug 30 00:37:57 2011, 美东) 提到:
my 2 cents:
允许额外花费O(n)空间么。。。
允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
当前计数器值放入新开的等大... 阅读全帖 |
|
s******n
发帖数: 3946 | 6 MinCost(1)为260？为啥阿，如果1年的话只修花60就行了。 |
|
l***i
发帖数: 1309 | 7 the last one is mincost flow problem. |
|
t******e
发帖数: 98 | 8 写mincost maxflow算法恐怕没几个interviewer知道，对方不懂的话还是不要用了，短
短30分钟里不太可能教会别人一个复杂算法。 |
|
g*********e
发帖数: 14401 | 9 minCost(first i houses, i th house with color x)
,
houses |
|
l***i
发帖数: 1309 | 10 maxflow
mincost flow
assignment problem and hungarian algorithm
Knuth-Morris-Pratt
Strassens' matrix multiplication
Bellman-Ford
Aho–Corasick
其实我是开玩笑的，以上应该都不会考。 |
|
|
l******e
发帖数: 470 | 12 一般匈牙利是指无权的。
网上km很多都有bug，要不根本就是算法理解错误，我记得我以前搜过，一个能用的没
找到
最后自己写了个mincost-flow了事，很容易写,比km应该容易写，而且速度不慢。 |
|
