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 1267 下沙的沙子有几粒?[DP]

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

分析,这题其实是H和D的组合排列问题,只不过要考虑期间累计的H和D的数量关系。

用DP来做,可以推导出:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

dp[][]前一个表示H的数量,后一个表示D的数量。

分上面那种情况是因为最后一个必然是H或者D,而此时可以考虑把新加的一个放在最后,因为假如加的是H,如果加在[i-1][j]中加入H,则最后一个依然是H或D,此时如果成立,那么依然属于[i-1][j]或[i][j-1]的情况。

所以推导出此递推关系。

以下是AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
__int64 dp[22][22];// 前面是H,后面是D
 
int main()
{
    dp[1][1] = 1;
    dp[2][1] = 2;
    dp[1][2] = 0;
    for(int i=1; i<=20; ++i)
        dp[i][1] = i;
    for(int i=2; i<=20; ++i)
        for(int j=2; j<=20; ++j)
            if(i >= j)
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            else
                dp[i][j] = 0;
    int m, n;
    while(cin >> m >> n)
        cout << dp[m][n] << endl;
}

看见网上还有这种做法的:
f(m,n) =( ((m+n)!)/((m!)*n!) )*(1-n/(m+1))
代码:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
using namespace std;
int main()
{
    int i,j,len=1,r=0,temp=0;
    int a[201][400]={0};
    a[1][0]=1;
    for(i=2;i<=200;i++)//求1……200的阶乘
    {
        for(j=0;j<len;j++)
            a[i][j] = a[i-1][j] * i;
        for(j=0,r=0;j<len;j++)
        {
            temp = a[i][j] + r;
            a[i][j] = temp % 10;
            r = temp /10;
        }
        while(r)
        {
            a[i][len++] = r%10;
            r /= 10;
        }
    }
    int m,n;
    while(cin>>m>>n)
    {
        r = 0;
        len = 400;//改成300就错了
        int b[500]={0};
        for(j=0;j<len;j++)
        {
            temp = a[m+n][j]*(m+1-n) + r;
            b[j] = temp % 10;
            r = temp /10;
        }
        while(r)
        {
            b[len++] = r%10;
            r /= 10;
        }
 
        for(j=len-1,r=0;j>=0;j--)
        {            //除法从高位到低位
            temp=r*10+b[j];
            b[j]=temp/(m+1);
            r=temp%(m+1);
        }
        while(!b[len])        //处理高位的零位
            len--;
 
        for(i=m;i>1;i--)//除m!
        {    
            for(j=len,r=0;j>=0;j--)  
                {            //除法从高位到低位
                temp=r*10+b[j];
                b[j]=temp/i;
                r=temp%i;
                }
            while(!b[len])        //处理高位的零位
            len--;
        }
 
        for(i=n;i>1;i--)//除n!
        {    
            for(j=len,r=0;j>=0;j--)  
                {            //除法从高位到低位
                temp=r*10+b[j];
                b[j]=temp/i;
                r=temp%i;
                }
            while(!b[len])        //处理高位的零位
            len--;
        }
 
        for(j=len;j>=0;j--)
            cout<<b[j];
        cout<<endl;
    }
    return 0;
}

SRM 494 DIV2 自己的第一次TC比赛

这是第一次参加TopCoder,也是第二次参加网络赛,第一次是去年的有道难题。

今天怎么说呢,有喜有忧吧。

首先对于TC不熟悉,而且对C++标准库用的也不是很习惯。导致第一题先开始没用map,而是想把first和second融合,然后排序,直接遍历vector。这个方法很麻烦,而且在compile时报错,于是我改成map,但是感觉不可能有错了,却还是报同样的错误,经过miyu提醒,原来是要用类表示出来,而我却是用函数表示的。。。。

汗一把,就因为这个问题,我花了20分钟去找错,结果第一题做完后只剩30多分钟了,而且第一题也只得了112.06分。

于是我抓紧看500的题,题目不难,我直接模拟了,很幸运的过了test,然后得了308.22分,我以为这次可以得400多分了,结果还不错,毕竟第一次做,还在250的题目上浪费了这么多。

结果,接下来的Challenge就让我郁闷了,居然500的题目被Cha了。。。

结果最后只有112.06分,排在700多名,没关系,毕竟第一次,下次加油了!

还有,要多熟悉以下C++标准库了!

刚看了以下rate,是934.绿色名字了,估计下次就会直线下降的。。。。

PS:睡觉了。。。已经凌晨3点多了。。。眼睛开始发花=。=

HDU/HDOJ 2512 一卡通大冒险

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

斯特林数,组合数学的知识。

斯特林数:

斯特林数出现在许多组合枚举问题中. 对第一类斯特林数 StirlingS1[n,m], 给出恰包含 m 个圈的 n 个元素 的排列数目. 斯特林数满足母函数关系 . 注意某些 的定义与 Mathematica 中的不同,差别在于因子 . 第二类斯特林数 StirlingS2[n,m]给出把 n 个可区分小球分配到m个不可区分的的盒子,且盒子没有空盒子的方法的数量. 它们满足关系 . 划分函数 PartitionsP[n]给出把整数 n 写为正整数的和,不考虑顺序的方法的数目. PartitionsQ[n]给出把整数 n 写为正整数的和,并且和中的整数是互不相同的 写法的数目

继续阅读HDU/HDOJ 2512 一卡通大冒险

最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++)

相关文章:

1.Dijkstra算法:

http://www.wutianqi.com/?p=1890

2.Floyd算法:

http://www.wutianqi.com/?p=1903

Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。Bellman-Ford算法的流程如下: 继续阅读最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++)