题目（选自软件设计师考试 2009年下半年 试题25、26）：

http://s14/mw690/6d79d83agx6BzjBMRZ34d&690

 

http://s6/mw690/6d79d83agx6BzjGXQQB35&690

正确答案：C B

看到这题后，我一开始感到很疑惑。发现题目中S1、S2、S3、S4这4个信号量并非是面向结点的（如果是面向结点的话，将正确答案代入无法推导到正确结果）。

 

首先，先来讲一下前驱图的概念：如原图，P1到P2有一条有向边，表示如果要执行P2，那么就要先执行P1，感觉类似于拓扑排序中的AOV网还有关键路径中的网，但是没有权值。再例如，对于点P3，要执行P1和P2后，才能执行P3。

浅谈

题目：http://www.tyvj.cn/Problem_Show.asp?id=1258

 

题意：中文题，题意就不讲了。

 

分析；一道经典的DP题。如果你是C或C++选手，你只能用字符串读入数据，为什么呢？因为每一行并没有告诉你有几个数字，只是让你通过换行符来判断每一层的状态。此题输入特别坑人，假如你TLE在第1和第3个点，那是因为数据的末尾有可能会有换行或空格，所以要读到EOF才能结束。

dp的思路应该是很明显，方程也很好写，对于第i层，它有可能是由输入的数据来决定前驱状态，所以方程就为：dp[i]=max(dp[i],dp[j]+tree[i]);  j为枚举i的所有前驱层，tree为每一层礼物的价值。

 

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
int tree[105],dp[105];
vector <int> Pre[105];

partition函数的作用是：将容器根据程序员的要求 划分成两个部分，属于整理算法。函数参数：partition(first,last,compare);//first为容器的首迭代器，last为容器的末迭代器，compare为比较函数（不可略写）。函数返回值：两个集合的分界处。

例题：输入n个数字，把奇数和偶数分别放置在容器的左边与右边。
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int &elem) {return elem%2;}
int main()
{
    vector <int> V;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        V.push_back(t);
    }
    vector <int> ::iterator it=partition(V.begin(),V.end(),compare);

randdom_shuffle函数的功能是：随机打乱一个序列。函数参数：random_shuffle(first,last);//first为容器的首迭代器，last为容器的末迭代器。该函数没有任何返回值。

这个函数很简单，直接看个例子：输入n个数字，输出打乱后的序列。
代码:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    srand((unsigned)time(0));
    int n;
    vector <int> V;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        V.push_back(t);
    }
    random_shuffle(V.begin(),V.end());
    for(vector <int> ::iterator iter=V.begin();iter!=V.end();iter++)
 &n

1. 1.        资源问题1
2. -----机器分配问题
3. F[I,j]:=max(f[i-1,k]+w[i,j-k])
4. 2.        资源问题2
5. ------01背包问题
6.    F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]);
7. 3.        线性动态规划1
8. -----朴素最长非降子序列
9.    F:=max{f[j]+1}
10. 4.        剖分问题1
11. -----石子合并
12. F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
13. 5.        剖分问题2
14. -----多边形剖分