动态规划

流水线调度问题

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll minThree(ll a,ll b,ll c)
{
    return min(min(a,b),c);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int m;
        cin>>m;
        vector<vector<ll>>p(3,vector<ll>(m+1));
        for(int i=0; i<3; i++)
            for(int j=0; j<m; j++)
                cin>>p[i][j];
        vector<vector<ll>>t(3,vector<ll>(3));
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
                cin>>t[i][j];
        ll ans[3][m+1]= {0};
        ans[0][0]=p[0][0];
        ans[1][0]=p[1][0];
        ans[2][0]=p[2][0];
        for(int j=1; j<m; j++)
            for(int i=0; i<3; i++)
                ans[i][j]=minThree(ans[0][j-1]+p[i][j]+t[0][i],ans[1][j-1]+p[i][j]+t[1][i],ans[2][j-1]+p[i][j]+t[2][i]);
        cout<<minThree(ans[0][m-1],ans[1][m-1],ans[2][m-1])<<"\n";
    }
    return 0;
}

区间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
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
const ll MAXN = 511, inf = 1000000000;
using namespace std;
ll n;
ll sum[MAXN];
ll son[MAXN][2];
ll p[MAXN], f[MAXN][MAXN], root[MAXN][MAXN];
ll solve(ll l, ll r)
{
    if(l > r) return 0;
    if(f[l][r] != inf * inf) return f[l][r];
    else
    {
        for(ll i = l; i <= r; ++i)
            if(solve(l, i - 1) + solve(i + 1, r) + sum[r] - sum[l - 1] < f[l][r])
            {
                f[l][r] = solve(l, i - 1) + solve(i + 1, r) + sum[r] - sum[l -
                          1];
                root[l][r] = i;
            }
        return f[l][r];
    }
}
int dfs(int l, int r)
{
    if(l > r) return -1;
    son[root[l][r]][0] = dfs(l, root[l][r] - 1);
    son[root[l][r]][1] = dfs(root[l][r] + 1, r);
    return root[l][r];
}
int main()
{
    scanf("%lld", &n);
    for(ll i = 1; i <= n; ++i)
        for(ll j = 1; j <= n; ++j)
            f[i][j] = inf * inf;
    for(ll i = 1; i <= n; ++i)
    {
        scanf("%lld", &p[i]);
        sum[i] = sum[i - 1] + p[i];
    }
    printf("%lld\n", solve(1, n));
    dfs(1, n);
    for(ll i = 1; i <= n; ++i)
        printf("%lld %lld\n", son[i][0], son[i][1]);
    return 0;
}

LIS最长上升子序列

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
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],dp[N];
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        dp[i]=1;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            if(a[j]<a[i])
            {
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}
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
#include<cstdio>
#include<algorithm>
using namespace std;
int a[40005];
int d[40005];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (n==0)  //0个元素特判一下 
    {
        printf("0\n");
        return 0;
    }
    d[1]=a[1];  //初始化 
    int len=1;
    for (int i=2;i<=n;i++)
    {
        if (a[i]>=d[len]) d[++len]=a[i];  //如果可以接在len后面就接上，如果是最长上升子序列，这里变成> 
        else  //否则就找一个最该替换的替换掉 
        {
            int j=upper_bound(d+1,d+len+1,a[i])-d;  
            //找到第一个大于它的d的下标，如果是最长上升子序列，这里变成lower_bound 
            d[j]=a[i]; 
        }
    }
    printf("%d\n",len);    
    return 0;
}

LCS最长公共子序列

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
#include<bits/stdc++.h>
using namespace std;
int dp[2010][2010];
//求最长公共子串
int ZiChuan(char *s1,char *s2)
{
    int l1=strlen(s1);
    int l2=strlen(s2);
    int ans=0;
    for(int i=0;i<=l1;i++)
        for(int j=0;j<=l2;j++)
            dp[i][j]=0;
    for(int i=1; i<=l1; i++)
        for(int j=1; j<=l2; j++)
        {
            if(s1[i-1]==s2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=0;
            if(ans<dp[i][j])
                ans=dp[i][j];
        }
    return ans;
}
//求最长公共子序列
int ZiXuLie(char *s1,char *s2)
{
    int l1=strlen(s1);
    int l2=strlen(s2);
    for(int i=0;i<=l1;i++)
        for(int j=0;j<=l2;j++)
            dp[i][j]=0;
    for(int i=1; i<=l1; i++)
        for(int j=1; j<=l2; j++)
        {
            if(s1[i-1]==s2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    return dp[l1][l2];
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        char s1[2010];
        char s2[2010];
        cin>>s1>>s2;
        cout<<ZiChuan(s1,s2)<<" "<<ZiXuLie(s1,s2)<<"\n";
    }
    return 0;
}

LCIS最长公共上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        dp[i][j]=dp[i-1][j];
        if(a[i]==b[j]){
            for(int k=1;k<j;k++){
            	if(b[j]>b[k]){
                	dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
				}  
			}
        }
    }
}

二分

1
2
3
4
5
6
lower_bound()：first和last中的 前闭后开 区间进行二分查找，
返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val，则返回last的位置，且last的位置是越界的
upper_bound()：在前闭后开区间查找，返回大于val的第一个元素位置
例如：一个数组number序列1,2,2,4.upper_bound(2)后，返回的位置是3（下标）也就是4所在的位置,
同样，如果插入元素大于数组中全部元素，返回的是last。(注意：数组下标越界)
binary_search()：若目标值存在则返回true，否则返回false