分类目录归档：动态规划

洛谷 P1373 小a和uim之大逃离

发表评论

自己博客上好像全是代码了，正经的题解还没多少。。。
代码还都是一堆看别人题解写出来的。
https://www.luogu.org/blog/yh1127/solution-p1373

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<iostream>
#include<cstring>
#define MOD 1000000007
using namespace std;
int f[805][805][17][2],a[805][805];
int n,m,k,ans;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    k++;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        cin>>a[i][j];
        f[i][j][a[i][j]][0]=1;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int p=0;p<=k-1;p++){
        f[i][j][p][1]+=f[i][j-1][(p+a[i][j])%k][0];
        f[i][j][p][1]%=MOD;
        f[i][j][p][1]+=f[i-1][j][(p+a[i][j])%k][0];
        f[i][j][p][1]%=MOD;
        f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k)%k][1];
        f[i][j][p][0]%=MOD;
        f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)%k][1];
                f[i][j][p][0]%=MOD;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        ans+=f[i][j][0][1];
        ans%=MOD;
    }
    cout<<ans;
}

洛谷 P1220 关路灯

发表评论

我递推啥都不会写垃圾死了，一道对我来说用递推非常难以解决的、难以思考的DP题目被我用记忆化递归解决了，0ms，高兴死我啦！
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，代码写的那么长。。

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
#include<iostream>
#include<cstring>
using namespace std;
int n,c;
int pos[55],power[55];
int prefixPower[55];
int f[55][55][2];
inline int getEnergy(int l,int r){
    return prefixPower[n]-prefixPower[r]+prefixPower[l-1];
}
int dp(int l,int r,int d){
    if(f[l][r][d]!=-1)return f[l][r][d];
    if(l==1&&r==n)return f[l][r][d]=0;
    if(l==1&&r<n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1);
    if(l>1&&r==n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0);
    else return f[l][r][d]=min(getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0),getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1));
}
int main(){
    ios::sync_with_stdio(false);
    memset(f,-1,sizeof(f));
    cin>>n>>c;
    for(int i=1;i<=n;i++)cin>>pos[i]>>power[i];
    for(int i=1;i<=n;i++)prefixPower[i]=prefixPower[i-1]+power[i];
    cout<<min(dp(c,c,0),dp(c,c,1));
}

洛谷 P1441 砝码称重

发表评论

先写了个两层搜索，后来又参考题解改了个搜索+动态规划。
题解：https://www.luogu.org/blog/yeyangrui/solution-p1441
60分搜索：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
bool mass[2005];
int weight[25];
bool visited[25];
void dfs(int pos,int num){
    if(pos==n+1)return;
    if(visited[pos]){
        dfs(pos+1,num);
        return;
    }
    mass[num+weight[pos]]=true;
    dfs(pos+1,num+weight[pos]);
    mass[num]=true;
    dfs(pos+1,num);
}
int getMassCounts(){
    memset(mass,false,sizeof(mass));
    dfs(1,0);
    int cnter=0;
    for(int i=1;i<=n*100;i++)if(mass[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

100分动规：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
int f[2005];
int weight[25];
bool visited[25];
int getMassCounts(){
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        for(int j=2000;j>=0;j--){
            if(j+weight[i]<=2000&&f[j]!=0)f[j+weight[i]]=1;
        }
    }
    int cnter=0;
    for(int i=1;i<=2000;i++)if(f[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

洛谷 P1066 2^k进制数

发表评论

50分的一个搜索写法：

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
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int result[205];
int pow2[10]={1,2,4,8,16,32,64,128,256,512};
int k,w;
inline void percolate(){
    for(int i=1;i<=203&&result[i]>10000;i++){
        result[i+1]+=result[i]/10000;
        result[i]%=10000;
    }
}
inline void dfs(int pos,int num){
    if(num==0)return;
    if((w%k==0?w/k:w/k+1)<pos)return;
    if(w%k!=0&&(w/k+1)==pos)num=min(pow2[w%k]-1,num);
    for(int i=1;i<=num;i++)dfs(pos+1,i-1);
    if(pos!=1){
        result[1]+=num;
        percolate();
    }
}
int main(){
    cin>>k>>w;
    dfs(1,pow2[k]-1);
    int flag=0;
    for(int i=204;i>0;i--){
        if(result[i])flag++;
        if(result[i]==0){if(flag)cout<<"0000";}
        else printf((flag==1?"%d":"%04d"),result[i]);
    }
}

100分写法：
参考题解：https://www.luogu.org/blog/user50852/solution-p1066

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<iostream>
#include<string>
#include<algorithm>
#define PINF 0x7fffffff
using namespace std;
struct bigInt { //For Non-negative Numbers
    // You must include header **iostream** and **string** before using this class!
private:
    string v;
    static string & bIsort(string & v) { //each char has reduced '0'
        for (int i = 0; i < v.length(); i++) {
            if (v[i] > 9) {
                if (i == v.length() - 1)v.append(1, v[i] / 10);
                else v[i + 1] += v[i] / 10;
                v[i] %= 10;
            }
        }
        return v;
    }
    static string lng2str(long long v) {
        string s = "";
        while (v) {
            s.append(1, v % 10 + '0');
            v /= 10;
        }
        reverse(s.begin(), s.end());
        return s;
    }
    static string& trimPre0(string& v3) {
        while (v3.length() != 0 && (*v3.begin()) == '0')v3.erase(v3.begin());
        if (v3.length() == 0)v3 = "0";
        return v3;
    }
public:
    bigInt() {
        v = "0";
    }
    bigInt(long long n) {
        v = lng2str(n);
    }
    bigInt(string s) {
        v = s;
    }
    bigInt& operator = (const bigInt & bI) {
        this->v = bI.v;
        return *this;
    }
    bigInt operator + (bigInt bI2) const {
        string s1 = v, s2 = bI2.v;
        if (s1.length() > s2.length())swap(s1, s2);
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int s1len = s1.length(), s2len = s2.length();
        for (int i = 0; i < s1len; i++)s2[i] += s1[i] - '0';
        for (int i = 0; i < s2len - 1; i++)if (s2[i] > '9') {
            s2[i + 1] += (s2[i] - '0') / 10;
            s2[i] = '0' + (s2[i] - '0') % 10;
        }
        if (s2[s2len - 1] > '9') {
            s2.append(1, '0' + (s2[s2len - 1] - '0') / 10);
            s2[s2len - 1] = '0' + (s2[s2len - 1] - '0') % 10;
        }
        reverse(s2.begin(),s2.end());
        return bigInt(s2);
    }
    bigInt operator - (bigInt bI2) const {
        string s1, s2;
        if ((*this) < bI2) {
            s1 = v; s2 = bI2.v;
        }
        else {
            s1 = bI2.v; s2 = v;
        }
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int s1len = s1.length(), s2len = s2.length();
        for (int i = 0; i<s1len; i++)s2[i] -= s1[i] - '0';
        for (int i = 0; i<s2len - 1; i++)if (s2[i]<'0') {
                s2[i + 1] -= 1;
                s2[i] += 10;
        }
        if (s2[s2len - 1] == '0')s2.erase(s2.end() - 1);
        reverse(s2.begin(), s2.end());
        return bigInt(trimPre0(s2));
    }
    bigInt operator * (bigInt bI2) const {
        string v1 = v, v2 = bI2.v;
        if (v2.length() > v1.length())swap(v1, v2);
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());
        string v3 = "";
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        for (int i = 0; i < v2.length(); i++)v2[i] -= '0';
        v3.resize(v1.length() + v2.length(), 0);
        for (int i = 0; i < v2.length(); i++) {
            for (int j = 0; j < v1.length(); j++) {
                v3[i + j] += v2[i] * v1[j];
            }
            bIsort(v3);
        }
        for (int i = 0; i < v3.length(); i++)v3[i] += '0';
        reverse(v3.begin(), v3.end());
        trimPre0(v3);
        return bigInt(v3);
    }
    bigInt operator / (long long bI2) const {
        string v1 = v;
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        long long v2 = bI2;
        string v3 = "";
        long long div = 0;
        for (int i = 0; i < v1.length(); i++) {
            div *= 10;
            div += v1[i];
            if (div < v2) {
                v3.append(1, '0');
                continue;
            }
            v3.append(lng2str(div / v2));
            div %= v2;
        }
        return bigInt(trimPre0(v3));
    }
    bool operator < (bigInt bI2) const {
        if (v.length() != bI2.v.length())return v.length() < bI2.v.length();
        for (int i = 0; i < v.length(); i++) {
            if (v[i] != bI2.v[i])return v[i] < bI2.v[i];
        }
        return false;
    }
    friend istream& operator >> (istream& in, bigInt& bI) {
        in >> bI.v;
        return in;
    }
    friend ostream& operator << (ostream& out, bigInt& bI) {
        out << bI.v;
        return out;
    }
};

bigInt ans=0,f[520][520];

int main(){
    int k,w;
    cin>>k>>w;
    int maxLen=w/k;
    if(w%k!=0)maxLen++;
    int radix=1<<k;
    maxLen=min(maxLen,radix-1);
    for(int i=1;i<=radix-1;i++)f[1][i]=1;
    for(int i=2;i<=maxLen;i++){
        int l;
        if(w%k==0)l=PINF;
        else if(i==maxLen)l=(1<<(w%k))-1;
        else l=PINF;
        for(int j=radix-i;j>0;j--){
            f[i][j]=f[i][j+1]+f[i-1][j+1];
            if(j<=l)ans=ans+f[i][j];
        }
    }
    cout<<ans;
}

洛谷 P1439 【模板】最长公共子序列

发表评论

这题不是LCS的裸题啊……。。基本上照抄的题解：
https://pks-loving.blog.luogu.org/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie

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>
using namespace std;
int a[100005],b[100005],map[100005],f[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];map[a[i]]=i;}
    for(int i=1;i<=n;i++){cin>>b[i];f[i]=0x7fffffff;}
    int len=0;
    f[0]=0;
    for(int i=1;i<=n;i++){
        int l=0,r=len,mid;
        if(map[b[i]]>f[len])f[++len]=map[b[i]];
        else{
            while(l<r){
                mid=(l+r)>>1;
                if(f[mid]>map[b[i]])r=mid;
                else l=mid+1;
            }
            f[l]=min(map[b[i]],f[l]);
        }
    }
    cout<<len;
}

洛谷 P1108 低价购买

发表评论

头一回自己写出来个这么难的动规，小小的激动一下。。
如果直接把100分的代码贴出来，也没啥用。我把分数逐渐增长的所有代码都贴出来，万一自己以后又做到这道题没有思路可作参考。
确实很麻烦。如果直接看100分的会一头雾水，还写不出来注释，思想太复杂了。只可意会。
想看简单题解的OIer可以去洛谷题解上看。
63分：

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
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[5005];
int dp[5005];
int ways[5005];
bool visited[65537];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> price[i];
    for (int i = 1; i <= n+1; i++) {
        int mDpV = 0, cWays = 1;
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    memset(visited, false, sizeof(visited));
                    visited[price[j]] = true;
                }
                if (dp[j] == mDpV && !visited[price[j]]) {
                    cWays += ways[j];
                    visited[price[j]] = true;
                }
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

73分：把memset的范围调小了

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[5005];
int dp[5005];
int ways[5005];
bool visited[65537];
int main() {
    cin >> n;
    price[0] = 65537;
    ways[0] = 1;
    int vmax = 0, vmin = 65537;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
        vmax = max(vmax, price[i]);
        vmin = min(vmin, price[i]);
    }
    for (int i = 1; i <= n+1; i++) {
        int mDpV = dp[0], cWays = 1;
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    memset(visited + vmin, false, sizeof(int)*(vmax - vmin + 1));
                    visited[price[j]] = true;
                }
                if (dp[j] == mDpV && !visited[price[j]]) {
                    cWays += ways[j];
                    visited[price[j]] = true;
                }
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

82分：不在每个j处都memset，而是利用版本号的想法，改为在i处更新。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[10000];
long long dp[10000];
long long ways[10000];
int visited[65540]; //[price][version()]
int main() {
    cin >> n;
    int vmax = 0, vmin = 65537;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
        vmax = max(vmax, price[i]);
        vmin = min(vmin, price[i]);
    }
    for (int i = 1; i <= n+1; i++) {
        long long mDpV = 0;
        long long cWays = 1;
        memset(visited, 0, sizeof(visited));
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    visited[price[j]] = mDpV;
                }
                if (dp[j] == mDpV && visited[price[j]]<mDpV) {
                    cWays += ways[j];
                    visited[price[j]] = mDpV;
                }
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

100分：参考别人题解发现了用后面替代前面的重要问题。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int price[10000];
long long dp[10000]; //DP 数组
long long ways[10000]; //方法数 数组
long long visited[65540][2]; // [price][0]代表当前最长降序子序列长度，[price][1]代表在此情况下的方法数
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> price[i];
    for (int i = 1; i <= n+1; i++) {
        long long mDpV = 0;
        long long cWays = 1;
        memset(visited, 0, sizeof(visited));
        for (int j = 1; j < i; j++) {
            if (price[j] > price[i]) {
                //当visited[price[j]][0]有更新时，用后面的替代前面的，因为相应的方法数也会有更新
                if (dp[j] == mDpV && visited[price[j]][0]==mDpV) {
                    cWays += ways[j];
                    cWays -= visited[price[j]][1];
                    visited[price[j]][1] = ways[j];
                }
                else if (dp[j] == mDpV && visited[price[j]][0]<mDpV) {
                    cWays += ways[j];
                    visited[price[j]][0] = mDpV;
                    visited[price[j]][1] = ways[j];
                }
                else if (dp[j] > mDpV) {
                    mDpV = dp[j];
                    cWays = ways[j];
                    visited[price[j]][0] = mDpV;
                    visited[price[j]][1] = ways[j];
                }
               
            }
        }
        dp[i] = mDpV + 1;
        ways[i] = cWays;
    }
    cout << dp[n+1]-1 << " " <<ways[n+1];
}

洛谷 P1541 乌龟棋

发表评论
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<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int a[355],b[6];
int f[45][45][45][45];
int safeF(int i,int j,int k,int l){
    if(i<0||j<0|k<0||l<0)return 0;
    else return f[i][j][k][l];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        int t;
        cin>>t;
        b[t]++;
    }
    for(int i=0;i<=b[1];i++)for(int j=0;j<=b[2];j++)for(int k=0;k<=b[3];k++)for(int l=0;l<=b[4];l++){
        f[i][j][k][l]=max(max(safeF(i-1,j,k,l),safeF(i,j-1,k,l)),max(safeF(i,j,k-1,l),safeF(i,j,k,l-1)))+a[i+2*j+3*k+4*l+1];
    }
    cout<<f[b[1]][b[2]][b[3]][b[4]];
}

洛谷 P1880 [NOI1995]石子合并

发表评论

转移方程是看别人的……
参考：易懂https://www.luogu.org/blog/user45556/solution-p1880
区间动规经典题目？

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int arr[205];
int presum[205];
int fMax[205][205], fMin[205][205];
int dfsMax(int l, int r) {
    if (l == r)return 0;
    if (fMax[l][r] != 0)return fMax[l][r];
    int dIJ = presum[r] - presum[l - 1];
    int mmax = 0;
    for (int k = l; k < r; k++) mmax = max(mmax, dfsMax(l, k) + dfsMax(k + 1, r) + dIJ);
    return fMax[l][r] = mmax;
}
int dfsMin(int l, int r) {
    if (l == r)return 0;
    if (fMin[l][r] != 0)return fMin[l][r];
    int dIJ = presum[r] - presum[l - 1];
    int mmin = 0x7fffffff;
    for (int k = l; k < r; k++)mmin = min(mmin, dfsMin(l, k) + dfsMin(k + 1, r) + dIJ);
    return fMin[l][r] = mmin;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    for (int i = n + 1; i <= 2*n; i++)arr[i] = arr[i - n];
    for (int i = 1; i <= 2 * n; i++)presum[i] = presum[i - 1] + arr[i];
    int mmin = 0x7fffffff;
    for (int i = 1; i <= n; i++) {
        mmin = min(mmin, dfsMin(i, i + n - 1));
    }
    cout << mmin << endl;
    int mmax = 0;
    for (int i = 1; i <= n; i++) {
        mmax = max(mmax, dfsMax(i, i + n - 1));
    }
    cout << mmax << endl;

}

洛谷 P1020 导弹拦截

发表评论

又是自己改了半天的一道题，忘了……

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
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n=1;
int arr[100005];
int f[100005];
int f2[100005];
int main() {
    while (cin >> arr[n])n++;
    n--;
    arr[0] = 50001;
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        int m = f[0];
        for (int j = 1; j < i; j++) {
            if (f[j]>m&&arr[j]>=arr[i]) {
                m = f[j];
            }
        }
        f[i] = m + 1;
    }
    cout << *max_element(f+1,f+n+1) << endl;
    arr[0] = 0;
    f2[0] = 0;
    for (int i = 1; i <= n; i++) {
        int m = f2[0];
        for (int j = 1; j < i; j++) {
            if (f2[j]>m&&arr[j]<arr[i]) {
                m = f2[j];
            }
        }
        f2[i] = m + 1;
    }
    cout << *max_element(f2+1,f2+n+1) << endl;
}