分类目录归档：动态规划

洛谷/USACO 01串 Stringsobits

发表评论

洛谷题号：P2727
参考题解：作者: 罗进瑶 更新时间: 2017-08-04 10:49 https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2727

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<cassert>
#include<map>
#include<queue>
using namespace std;
long long dp[40][40];//dp[i][j]表示长度为i，最多含有j个1的二进制数的个数
int main(){
    ios::sync_with_stdio(false);
    long long n, l, i;
    cin >> n >> l >> i;
    for (int i = 0; i <= n; i++)dp[i][0] = dp[0][i] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= l; j++){
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    long long k = i;
    for (int i = n; i >= 1; i--){
        if (k > dp[i - 1][l]){
            cout << "1";
            k -= dp[i - 1][l];
            l--;
        }
        else cout << "0";
    }
    cout << endl;
}

洛谷 奶牛家谱 Cow Pedigrees

发表评论

毫不夸张的说：USACO里2.3节最难的动规、、、
基本是照着题解一个字一个字对的。。。。
题号：1472

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
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define MOD 9901
using namespace std;
int n, k;
long long f[210][110],dp[210][110]; //必须是long long
int main(){
    cin >> n >> k;
    //if (n % 2 == 0){
    //  cout << 0 << endl;
    //  return 0;
    //}
    dp[1][1] = 1; f[0][0] = 1;
    for (int i = 1; i <= k; i++)f[1][i] = f[0][i] = 1;
    for (int i = 3; i <= n; i += 2){ //i:Node Num;j:depth
        int j = 1; while ((1 << j) - 1 < i)j++;
        for (; j <= k; j++){
            for (int l = 1; l <= i - 1; l += 2){
                dp[i][j] += dp[l][j - 1] * f[i - l - 1][j - 2];
                dp[i][j] += f[l][j - 2] * dp[i - l - 1][j - 1];
                dp[i][j] += dp[l][j - 1] * dp[i - l - 1][j - 1];
            }
            dp[i][j] %= MOD;
        }
        for (int j = 1; j <= k; j++)f[i][j] = (f[i][j - 1] + dp[i][j]) % MOD;
    }
    cout << dp[n][k] << endl;
}

洛谷 过河

发表评论

题号：1052
参考题解：
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1052
作者: CoolTeam 更新时间: 2015-08-11 18:26
作者: shutdown 更新时间: 2013-07-30 20:20
作者: VengefulSpirit 更新时间: 2013-06-25 11:17
作者: sb123 更新时间: 2017-08-07 17:58

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int f[20005];
int Mk[105],M[105];
//ifstream cin("in.txt");
//ofstream cout("out.txt");
int main(){
    ios::sync_with_stdio(false);
    int l, s, t, m,ans=0;
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; i++){
        cin >> Mk[i];//存入M的临时数组
    }
    if (s == t){//当s==t时是特殊情况，只需判断为s/t倍数的点有无石子即可 ；参考CoolTeam。为啥用动态规划过不了，我也不知道
        for (int i = 1; i <= m; i++){
            if (Mk[i] % s == 0)ans++;
        }
        cout << ans;
        return 0;
    } //否则需要使用动态规划
    memset(f, 0x7f, sizeof(f));
    f[0] = 0;
    sort(Mk + 1, Mk + m + 1); //先给临时数组排个序
    for (int i = 1; i <= m; i++){
        if (Mk[i] - Mk[i - 1] >= 100)M[i] = M[i - 1] + 100; //如果两相邻石子之间距离大于100，就将他们之间的距离缩小到100 ；参考shutdown的结论，VengefulSpirit的证明过程
        else M[i] = M[i - 1] + Mk[i] - Mk[i - 1];
    }
    int M_cnt = 1;
    for (int i = 1; i <= M[m]+t; i++){ //比较容易的动态规划 ；参考sb123的动规转移方程
        for (int j = i-s; j >= max(i - t,0); j--){
            f[i] = min(f[j], f[i]);
        }
        if (M[M_cnt] == i){
            f[i]++;
            M_cnt++;
        }
    }
    ans = 10000;
    for (int i = M[m] + t-1; i >= M[m]; i--)ans = min(ans, f[i]);  //遍历从最后一个石子到最后一个石子+t-1的最短距离
    cout << ans;
}

20180805更新，表示缩点/离散化恶心死了，写了半天60，迫不得已看题解了。、
参考题解：https://www.luogu.org/blog/GXu/solution-p1052
https://peerless.blog.luogu.org/guo-he-xie-ti-bao-gao

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>
#include<functional>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int l;
int s, t, m;
int pos[105];
int d[105];
bool stone[400000];
int f[400000];
int main() {
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; i++)cin >> pos[i];
    sort(pos + 1, pos + m + 1);
    for (int i = 1; i <= m; i++)d[i] = (pos[i] - pos[i - 1]) % 2520;
    for (int i = 1; i <= m; i++) {
        pos[i] = pos[i - 1] + d[i];
        stone[pos[i]] = true;
    }
    l = pos[m];
    for (int i = 1; i <= l + t; i++)f[i] = m;
    for (int i = 1; i <= l + t; i++) {
        for (int j = s; j <= t; j++) {
            if (i >= j)f[i] = min(f[i], f[i - j]);
            f[i] += stone[i];
        }
    }
    int ans = m;
    for (int i = l; i < l + t; i++)ans = min(ans, f[i]);
    cout << ans;
}

洛谷 传纸条

发表评论

题号：1006
同方格取数，只不过是有个别的地方需要一些变动。我傻傻的有一些地方没变……2333

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<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int m,n;
int f[55][55][55][55],arr[55][55];
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            for (int k = 1; k <= m; k++){
                for (int l = 1; l <= n; l++){
                    f[i][j][k][l] = max(f[i - 1][j][k - 1][l], f[i][j - 1][k - 1][l]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l - 1]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l - 1]);
                    if (i == k && j == l)f[i][j][k][l] += arr[i][j];
                    else f[i][j][k][l] += arr[i][j] + arr[k][l];
                }
            }
        }
    }
    cout << f[m][n][m][n];
}

20180802
做的烦得要死。。。上面的代码没看懂^^^^……………….
https://www.luogu.org/blog/user20197/solution-p1006
https://www.luogu.org/blog/user26182/solution-p1006

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int m, n;
int arr[205][205];
int f[55][55][55][55];
int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> arr[i][j];
    for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)for (int k = 1; k <= m; k++)for (int l = j + 1; l <= n; l++) {
        f[i][j][k][l] = max(max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]), max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1])) + arr[i][j] + arr[k][l];
    }
    cout << f[m][n-1][m-1][n];
}

洛谷 方格取数

发表评论

题号：1004
这题还是比较简单的……虽然我看了题解，但是还是能看得懂的。。
参考题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1004
作者: sb123 更新时间: 2017-08-07 14:52

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<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n;
int f[12][12][12][12],arr[12][12];
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    int rf1, rf2, rf3;
    while (cin >> rf1 >> rf2 >> rf3){
        if (rf1 == 0 && rf2 == 0 && rf3 == 0)break;
        arr[rf1][rf2] = rf3;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            for (int k = 1; k <= n; k++){
                for (int l = 1; l <= n; l++){
                    f[i][j][k][l] = max(f[i - 1][j][k - 1][l], f[i][j - 1][k - 1][l]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l - 1]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l - 1]);
                    if (i == k && j == l)f[i][j][k][l] += arr[i][j];
                    else f[i][j][k][l] += arr[i][j] + arr[k][l];
                }
            }
        }
    }
    cout << f[n][n][n][n];
}

洛谷 Likecloud-吃、吃、吃

发表评论

题号：1508
感动哭，第一个自己不用想状态转移方程就写出来的动规超级简单题……我是有多辣鸡……
这样的题一天做20道都没问题啊，要是NOIP全考这个就好了（逃）

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n, m;
int f[205][205],arr[205][205];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            f[i][j] = max(max(f[i - 1][j], f[i - 1][j - 1]), f[i - 1][j + 1]) + arr[i][j];
        }
    }
    cout << max(max(f[n][m / 2 + 1],f[n][m/2]),f[n][m/2+2]);
}

20180802更新：
呃呃呃。。。。因为之前做过这样的题所以才觉得很简单。。。。。。。。。。。

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<cstring>
#include<algorithm>
using namespace std;
int m, n;
int arr[205][205];
int main() {
    memset(arr, 0x80, sizeof(arr));
    cin >> m >> n;
    for (int i = 1; i <= n; i++)arr[0][i] = 0;
    arr[m+1][(n + 1) / 2] = 0;
    for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> arr[i][j];
    for (int i = m; i >= 0; i--) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] += max(max(arr[i + 1][j - 1], arr[i + 1][j]), arr[i + 1][j + 1]);
        }
    }
    int  mmax = 0;
    for (int i = 1; i <= n; i++) {
        mmax = max(mmax, arr[0][i]);
    }
    cout << mmax;
}

洛谷 [USACO1.5]数字三角形 Number Triangles

发表评论

题号：1216

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
#include<iostream>
#include<algorithm>
#include<string>
#define INF 2e9
using namespace std;
int n, arr[1005][1005];
int f[1005][1005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + arr[i][j];
        }
    }
    int m = 0;
    for (int i = 1; i <= n; i++){
        if (f[n][i] > m)m = f[n][i];
    }
    cout << m;
}

洛谷 尼克的任务

发表评论

题号：P1280
参考：http://blog.csdn.net/zhhx2001/article/details/52213855
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1280
作者: Radium_ 更新时间: 2016-08-25 12:58

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<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,k;
struct s{
int start;
int duration;
bool operator < (s & o1){
    return start<o1.start;
}
}info[10005];
int f[10005];
int taskptr;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=k;i++)cin>>info[i].start>>info[i].duration;
    sort(info+1,info+k+1);
    taskptr=k;
    for(int i=n;i>=1;i--){
        if(info[taskptr].start!=i)
            f[i]=f[i+1]+1;
        else
            while(info[taskptr].start==i){
                f[i]=max(f[i],f[i+info[taskptr].duration]);
                taskptr--;
            }
    }
    cout<<f[1];
}

20180802更新：
查看的题解：https://www.luogu.org/blog/user3573/solution-p1280

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<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, k;
struct task {
    int p, t;
    bool operator < (const task& t2) const {
        return p > t2.p;
    }
}ts[10005];
int f[10005];
int main(){
    cin >> n >> k;
    for (int i = 1; i <= k; i++)cin >> ts[i].p >> ts[i].t;
    sort(ts + 1, ts + k + 1);
    int tsptr = 1;
    for (int i = n; i > 0; i--) {
        if (ts[tsptr].p != i) {
            f[i] = f[i + 1] + 1;
            continue;
        }
        while (ts[tsptr].p == i) {
            f[i] = max(f[i], f[i + ts[tsptr].t]);
            tsptr++;
        }
    }
    cout << f[1];
}

洛谷 金明的预算方案

发表评论

题号：P1064
一维滚动数组优化。

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int v[65],p[65],q[65],w[65];
int q1[65],q2[65];
int iptr;
int f[35000];
void insert_subgood(int main,int sub){
    if(q1[main]==0)q1[main]=sub;
    else q2[main]=sub;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        w[i]=v[i]*p[i];
        if(q[i]!=0){
            insert_subgood(q[i],i);
        }
    }
    for(int i=1;i<=m;i++){
        if(q[i]!=0)continue;
        for(int j=n;j>=0;j--){
            if(j-v[i]>=0)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            if(q1[i]!=0&&j-v[i]-v[q1[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]]+w[i]+w[q1[i]]);
            if(q2[i]!=0&&j-v[i]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q2[i]]]+w[i]+w[q2[i]]);
            if(q1[i]!=0&&q2[i]!=0&&j-v[i]-v[q1[i]]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]-v[q2[i]]]+w[i]+w[q1[i]]+w[q2[i]]);
        }
    }
    cout<<f[n];
}