Algorithm 版 (精华区)

发信人: ssos (存在与虚无·守拙), 信区: Algorithm
标  题: [合集]Valla的702一定要用DP做吗?
发信站: 哈工大紫丁香 (2002年08月13日08:18:21 星期二), 站内信件


────────────────────────────────────────
 pamws (书虫)                         于 2002年08月10日11:54:14 星期六 说道:

我的递归的方法(下文)肯定要超时的， 网上说必须要用DP.
不过会不会有别的方法呢？
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
int count(bool * pp, int sz, int last, bool decrease=false) {
    int result=0;
    bool exist=false;
    for (int i=0; i<sz; i++) {
        if (pp[i]) continue; else exist=true;
        if (decrease && i>=last) continue;
        if (!decrease && i<=last) continue;
        pp[i]=true;
        result+=count(pp, sz, i, !decrease);
        pp[i]=false;
    }
    if (!exist) return 1;
    else return result;
}
int main(void) {
    #ifndef ONLINE_JUDGE
    freopen("702.in", "r", stdin);
    freopen("702.out", "w", stdout);
    #endif
    int num=0;
    int cap=0;
    while (scanf("%d %d", &num, &cap)!=EOF) {
        bool * pp=new bool[num];
        for (int i=0; i<num; i++) {
            pp[i]=false;
        }
        if (cap==1) {
            pp[cap-1]=true;
            pp[1]=true;
            pp[2]=true;
            printf("%d\n", count(pp, num, 1));
        } else {
            pp[cap-1]=true;
            printf("%d\n", count(pp, num, cap-1, true));
        }
    }
    return 0;
}

────────────────────────────────────────
 sino (仿佛永远分离 却又终身相依)     于 2002年08月10日15:32:33 星期六 说道:

这题什么意思啊，没看明白的说..
【 在 pamws (书虫) 的大作中提到: 】
: 我的递归的方法(下文)肯定要超时的， 网上说必须要用DP.
: 不过会不会有别的方法呢？
: #include <stdio.h>
: #include <stdlib.h>
: #include <fcntl.h>
: int count(bool * pp, int sz, int last, bool decrease=false) {
:     int result=0;
:     bool exist=false;
:     for (int i=0; i<sz; i++) {

────────────────────────────────────────
 lizhenguo (Biometrics)               于 2002年08月10日15:58:16 星期六 说道:

他给的最后一个数据是不是有问题啊？
4个人，队长身高最矮，那么排第二的人应该是身高第二矮，这样确定
两个人，剩下两个人任意，应该是2种情况吧。
pamws给解释一下？
【 在 sino (仿佛永远分离 却又终身相依) 的大作中提到: 】
: 这题什么意思啊，没看明白的说..
: 【 在 pamws (书虫) 的大作中提到: 】
: : 我的递归的方法(下文)肯定要超时的， 网上说必须要用DP.
: : 不过会不会有别的方法呢？
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <fcntl.h>
: : int count(bool * pp, int sz, int last, bool decrease=false) {
: :     int result=0;
: :     bool exist=false;
: :     for (int i=0; i<sz; i++) {

────────────────────────────────────────
 pamws (书虫)                         于 2002年08月10日16:01:04 星期六 说道:

e.g. the queue of players, {4} is captain
            @
         @  |
      @  |  |
   @  |  |  |
   |  |  |  |
   ^  ^  ^  ^
No 1  2  3 {4}
then the following schemes are valid
(captain comes first, being taller than his neighbour if possible
and the full queue in zigzag) 
1
   @        
   |     @       
   |  @  |       
   |  |  |  @      
   |  |  |  |      
   ^  ^  ^  ^      
2
   @            
   |     @      
   |     |  @    
   |  @  |  |   
   |  |  |  |   
   ^  ^  ^  ^   
so the number of valid alignment is 2.
【 在 sino (仿佛永远分离 却又终身相依) 的大作中提到: 】
: 这题什么意思啊，没看明白的说..
: 【 在 pamws (书虫) 的大作中提到: 】
: : 我的递归的方法(下文)肯定要超时的， 网上说必须要用DP.
: : 不过会不会有别的方法呢？
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <fcntl.h>
: : int count(bool * pp, int sz, int last, bool decrease=false) {
: :     int result=0;
: :     bool exist=false;
: :     for (int i=0; i<sz; i++) {

────────────────────────────────────────
 pamws (书虫)                         于 2002年08月10日16:02:38 星期六 说道:

必须要站成一高一矮(zigzag)， captain最矮的话应该是 1 3 2 4.
【 在 lizhenguo (Biometrics) 的大作中提到: 】
: 他给的最后一个数据是不是有问题啊？
: 4个人，队长身高最矮，那么排第二的人应该是身高第二矮，这样确定
: 两个人，剩下两个人任意，应该是2种情况吧。
: pamws给解释一下？
: 【 在 sino (仿佛永远分离 却又终身相依) 的大作中提到: 】
: : 这题什么意思啊，没看明白的说..

────────────────────────────────────────
 lizhenguo (Biometrics)               于 2002年08月10日16:30:13 星期六 说道:

他所说的DP是不是指递推求n个数的zigzag排法啊
zigzag(n)=zigzag(n-1)*(n-2)+(zigzag(n-1)-1)*2
zigzag(3)=3
感觉一般DP能解决的问题，其他方法在规模很大的时候解决的可能性
比较小
【 在 pamws (书虫) 的大作中提到: 】
: 必须要站成一高一矮(zigzag)， captain最矮的话应该是 1 3 2 4.
: 【 在 lizhenguo (Biometrics) 的大作中提到: 】
: : 他给的最后一个数据是不是有问题啊？
: : 4个人，队长身高最矮，那么排第二的人应该是身高第二矮，这样确定
: : 两个人，剩下两个人任意，应该是2种情况吧。
: : pamws给解释一下？

────────────────────────────────────────
 pamws (书虫)                         于 2002年08月10日18:11:33 星期六 说道:

zigzag(3)=4
3 1 2  ↓↑
1 3 2  ↑↓
2 1 3  ↓↑
2 3 1  ↑↓
【 在 lizhenguo (Biometrics) 的大作中提到: 】
: 他所说的DP是不是指递推求n个数的zigzag排法啊
: zigzag(n)=zigzag(n-1)*(n-2)+(zigzag(n-1)-1)*2
: zigzag(3)=3
: 感觉一般DP能解决的问题，其他方法在规模很大的时候解决的可能性
: 比较小
: 【 在 pamws (书虫) 的大作中提到: 】
: : 必须要站成一高一矮(zigzag)， captain最矮的话应该是 1 3 2 4.

────────────────────────────────────────