HDU/HDOJ 1158 Employment Planning(DP)

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1158

不知道为啥,这道DP把我脑袋快转晕了,有个地方想到了,可就是转不过去,真晕菜。

不过历经2小时,还是写出来了,这花的时间,真囧。。。。

分析:

DP,这一题数据范围没给出,不严谨。经测试,公认数量开105就行了,工资我现开始开0xffff,然后WA了,接着开了0x3ffffff,就AC了。

数组dp[i][j]表示第i个月员工数为j的总花费。

这题逐层(月)考虑,在上一层顺序遍历每一个dp[i-1][j] != INF的:

1.如果上一层(月)(即j)比本层(月)要求的人数(即man[i])少,则只需要雇佣相差的人数

2.如果上一层比本层要求人数多,则在man[i]和j之间,dp各个情况就行。

继续阅读HDU/HDOJ 1158 Employment Planning(DP)

HDU/HDOJ 1116 Play on Words(并查集+欧拉通路)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1116

离散数学的知识,囧,这一块没怎么学,基础很薄弱啊。

不过对于欧拉回路/通路的结论,倒是不难推出。

欧拉通路:除首尾结点外,其余结点入度等于出度,起点出度减入度等于1,终点入度减出度等于1

欧拉回路:所有结点的入度都等于出度

思路:将每一个单词的首尾字母当做结点,首尾字母间连线,判断最后形成的有向图能否形成欧拉通路/回路,用并查集。
继续阅读HDU/HDOJ 1116 Play on Words(并查集+欧拉通路)

HDU/HDOJ 2151 Worm(DP)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2151

先开始用的BFS,结果爆栈了,然后换成DP~~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <string>
using namespace std;
 
int N, P, M, T;
 
// dp[M][T];
// 表示在M时间上,走到T的方案数
// dp[M][T] = dp[M-1][T-1] + dp[M-1][T+1]
// 初始化dp[0][P] = 1;
int dp[105][105];
 
int main()
{
    while(cin >> N >> P >> M >> T)
    {
        memset(dp, 0, sizeof(dp));
        dp[0][P] = 1;
        for(int i=1; i<=M; ++i)
            for(int j=1; j<=N; ++j)
            {
                if(j-1 >= 1)
                    dp[i][j] += dp[i-1][j-1];
                if(j+1 <= N)
                    dp[i][j] += dp[i-1][j+1];
            }
 
        cout << dp[M][T] << endl;
    }
}
 
/*
int cnt;
 
void BFS(int vis, int time)
{
    if(time==M && vis==T)
    {
        ++cnt;
        return ;
    }
    if(vis == T)
        return;
 
    if(vis<1 || vis>N)
        return;
 
    if(vis >= 2)
        BFS(vis-1, time+1);
    if(vis <= N-1)
        BFS(vis+1, time+1);
}
 
int main()
{
    while(cin >> N >> P >> M >> T)
    {
        cnt = 0;
        BFS(P, 0);
        cout << cnt << endl;
    }
}
*/

HDU/HDOJ 2717 Catch That Cow(BFS)

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=2717

基本的BFS,注意在Teleporting时,考虑if的条件,具体见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <queue>
using namespace std;
 
int N, K;
int line[100005];
 
void BFS()
{
    queue<int> que;
    que.push(N);
    line[N] = 1;
 
    while(!que.empty())
    {
        int tmp = que.front();
        que.pop();
 
        if(tmp == K)
            break;
 
        int next = tmp-1;
        if(next>=0 && !line[next])
        {
            que.push(next);
            line[next] = line[tmp] + 1;
        }
 
        next = tmp+1;
        if(next>=0 && !line[next])
        {
            que.push(next);
            line[next] = line[tmp] + 1;
        }
 
        next = tmp*2;
        if(next<=100000 && !line[next] && next-K<K-tmp)
        {
            que.push(next);
            line[next] = line[tmp] + 1;
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d %d", &N, &K) != EOF)
    {
        memset(line, 0, sizeof(line));
        if(N >= K)
            line[K] = N-K+1;
        else
            BFS();
        printf("%d\n", line[K]-1);
 
    }
 
}

HDU/HDOJ 1280 前m大的数(sort || STL priority_queue)

题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1280

我直接用的STL的priority_queue做的~~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <queue>
using namespace std;
 
int N, M;
int arr[3005];
 
int main()
{
    //freopen("input.txt", "r", stdin);
    priority_queue<int> pq;
    while(scanf("%d %d", &N, &M) != EOF)
    {
        for(int i=0; i<N; ++i)
            scanf("%d", &arr[i]);
        for(int i=0; i<N; ++i)
            for(int j=i+1; j<N; ++j)
                pq.push(arr[i]+arr[j]);
        for(int i=0; i<M; ++i)
        {
            if(i != 0)
                printf(" ");
            printf("%d", pq.top());
            pq.pop();
        }
        printf("\n");
    }
}