|
|
|
|
|
|
|
复制本帖HTML代码
|
|
高亮:
今天贴
X 昨天贴
X 前天贴
X |
Paint Disk 那道题非常简单。
给 m 种color, N个sectors，有多少种paint的方法
paint 第一个sector有 m 种可能性，paint 第二个sector有 m-1 种可能性，一直到 第 n 个sector. 这时会有重复的可能，即第一个和最后一个sector是同一种颜色，把这些情况减去即可。
第一个和最后一个sector重复的情况有多少种呢？如果把第一个sector和最后一个sector看成是一个sector，那么每种重复的情况，恰好是 m 种color, N-1 个 sector的情况。所以recursion 就是
PD(m, n) = m*(m-1)^(n-1) - PD(m, n-1)
基本情况有若干种，请自己去分析好了，不再多说。
最后一道题目非常难，题目的意思是，24=2*12=3*8=4*6=2*2*6=...
{2, 12}是24的一个set，{3,8}也是24的一个set，{2,12}和{12, 2}算同一个set，{24}也是{24}的一个set。24有7个这样的set。要你算出若干数的set的个数，并且把最大的那个数以及它的set数找出来。
这道题很难。必须用Dynamic Programming才能做出来并且不超时。我用recursion做出来，3个accept，7个超时。想想给的数可能是1000,000，如果recursion做，它的用时该多少啊？
就算用Dynamic Programming 也很难想出algorithm。请参考以下一段code
int results[] = new int [max+1];
results[1] = 1;
for (int i=2; i<=max; i++) {
for (int j=1; j<=max/i; j++) {
results[i*j] += results[j];
}
//建议这里加一段code把results print出来看看比较直观
}
.
|
| 欢迎来到华新中文网，踊跃发帖是支持我们的最好方法! |
*签名档字数限制在200以内。
|
|
－