这几天寒假集训的算法总结(以DP为主)

这篇博客主要用来记录一下这几天学的算法
1. 普通DP：
主要是动态转移方程很难想到，比如说第一天的免费馅饼，开始来晚了，只听了一半，刚好怎么推方程的那一部分我没有听到。没办法，自己去找网上的博客，然后就发现了一种神奇的方法：
1：首先我们先要有一个矩阵martix~~（中黑客帝国的毒太深了）~~，其中martix的横坐标为time，纵坐标为位子place，这样我们就可以存入每个时间所对应的位置
2：然后你就懂了吧，这样我们可以转换成如何从time=0，place=5这个位子出发，到达time为规定时间的点的最小花费。
（ps：这个规定时间只要在读入时对每次输入的时间取max即可得到）
3:然后在扫一遍time=规定时间那一行的数据，求出这行数据的最大值就可以找到本题的答案了
2:区间DP：
这里先说一个比较坑的地方（论区间DP的正确打开方式)：
首先我们要枚举长度i，再枚举左端点l,这样右端点的值为l+i-1;
这样我们才能从更小的区间转移到更大的区间
区间DP就是从更小的区间中找出此时的状态，这里以匹配括号那道题为例。

题目：
如果有一个全由括号组成的字符串，如何找出其中最长的括号序列长度?(括号序列即匹配的括号的序列)
题解：
这道题目是一个区间DP，我们设dp[l][r]为l~r中的最长括号序列长度,用arr存入输入的字符串。然后我们进行分类讨论:
1：如果

l==r;

那么

dp[l][r]=0;

然后

continue;

2：如果

arr[l]=='(' && arr[r]==')'||arr[l]=='[' && arr[r]==']';

那么

dp[l][r]=dp[l+1][r-1]+2;

3: 然后我们再

int ans_max=-1;
for (int k=l;k<r;k++){
    ans_max=max(ans_max,dp[l][k]+dp[k+1][r]);
}
dp[l][r]=ans_max;

这是为了找出类似于"()()()"这样的情况的最大值

最后再用这样的代码

dp[l][r]=max(max(dp[l+1][r],dp[l][r-1]),dp[l][r]);

判断两边不相等的情况然后

cout<<dp[1][length]<<endl;//length为输入字符串的长度

即可。

3：树形DP，这个学的不好就不讲了，当然还是要贴一份树的遍历的代码滴!~~要不然这篇文章就太水了~~

//有根树
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

vector <int> map[5000];
int  book[5000];

void add(int x,int y){//X is father,y is son.
    map[x].push_back(y);
}

void dfs(int x){
    vector<int>::iterator it;
    for (it=map[x].begin();it!=map[x].end();it++){
        cout<<*it<<endl;//输出儿子
        dfs(*it);
    }

    return ;//返回

}

int main(){

    //调试用
    freopen ("input.in","r",stdin);

    int n;//n个关系
    cin>>n;
    int temp_x,temp_y;//Temp_x is father,temp_y is son.
    for (;;){
        cin>>temp_x>>temp_y;
        if (temp_x==0&&temp_y==0) break;
        book[temp_y]++;
        add(temp_x,temp_y);
    }

    //找根
    int root;
    for (int i=1;i<=n;i++){
        if (book[i]==0){
            root=i;
        }
    }

    dfs (root);

    return 0;

}

算法总结就到这里吧，FIGHTING！

lixiao189的博客

博客

评论