P1006 [NOIP2008 提高组] 传纸条

题解:
还是从后往前考虑：考虑从哪个点可以到当前的状态，然后把结果统计一下。

主要的难点其实在于不能经过同一个点两次，由因为从右下走到左上和左上走到右下其实是完全一样的，所以可以看成走两次从左上到右下的不同线路，且一条线路总是在另一条线路的上方。

注意到数据范围是50，足以支持四维dp的时间复杂度，所以考虑直接四维枚举两条路径的xy轴，并在枚举时保证第一条线路时刻位于第二条线路的上方即可。

代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 60;
int a[N][N];

int f[N][N][N][N];

int main(){
    int n,m;
    cin>>m>>n;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            for(int p = i + 1; p <= m; p++){
                for(int q = 1; q < j; q++){
                    //两个点的四种状态取最大值
                    f[i][j][p][q] = max(f[i - 1][j][p - 1][q], 
                                    max(f[i - 1][j][p][q - 1], 
                                    max(f[i][j - 1][p - 1][q], 
                                    f[i][j - 1][p][q - 1]))) 
                                    + a[i][j] 
                                    + a[p][q];
                }
            }
        }
    }
    printf("%d", f[m - 1][n][m][n - 1]);

P1052 [NOIP2005 提高组] 过河

题解:

独木桥的长度很长，但是石子的个数很少，可以预见的是桥的很多位置是大段的空白，所以直接把空白部分删掉就得了(将大于1000距离的两个相邻石子记为距离1000)...

至于这个1000的取法，实际上就是考虑数组是否能装下就行了，还有就是和S，T的大小有关系，貌似是只要大于S * T 就行了。

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int stone[N];
int bg[N];
bool mp[100010];
int f[100010];
int ans = 0x3f3f3f3f;

int main(){
    memset(f, 0x3f3f3f3f, sizeof f);
    memset(mp, false, sizeof mp);
    int l,s,t,m;
    cin>>l>>s>>t>>m;
    for(int i = 1; i <= m; i++) scanf("%d", &stone[i]);
    sort(stone + 1, stone + 1 + m);
    if(s == t){
        ans = 0;
        for(int i = 1; i <= m; i++){
            if(stone[i] % t == 0){
                ans++;
            }
        }
        printf("%d", ans);
        return 0;
    }
    for(int i = 1; i <= m; i++){
        if(stone[i] - stone[i - 1] > 1000){ //如果大于1000，直接记为1000
            bg[i] = bg[i - 1] + 1000; 
        } else {
            bg[i] = stone[i] - stone[i - 1] + bg[i - 1];
        }
        mp[bg[i]] = true;
    }
    f[0] = 0;
    for(int i = 1; i <= bg[m] + t - 1; i++){
        for(int j = s; j <= t && j <= i; j++){
            f[i] = min(f[i], f[i - j]);
            if(mp[i]) f[i]++;

        }
    }
    for(int i = bg[m]; i <= bg[m] + t - 1; i++){
        //printf("%d ", f[i]);
        ans = min(ans , f[i]);
    }
    printf("%d", ans);
}

P1130 红牌

简单的dp，特殊处理一下跳转到0的情况就好了

#include<bits/stdc++.h>
using namespace std;

int p[2010][2010];
int f[2010][2010];

int main(){
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &p[j][i]);
        }
    }
    for(int i = 1; i <= n; i++){
        f[i][0] = min(f[i - 1][0] + p[i - 1][0], f[i - 1][m - 1] + p[i - 1][m - 1]);
        for(int j = 1; j < m; j++){
            f[i][j] = min(f[i - 1][j] + p[i - 1][j], f[i - 1][j - 1] + p[i - 1][j - 1]);
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i = 0; i < m; i++){
        ans = min(f[n][i], ans);
    }
    printf("%d ", ans);
}

P1063 [NOIP2006 提高组] 能量项链

区间DP

类似石子合并，用延长一倍的方式去处理环。

从小到大枚举dis，感觉这类题还是有模板的。

#include<bits/stdc++.h>
using namespace std;

const int N = 220;
int n;
int a[N];
int f[N][N];

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        a[i + n] = a[i]; 
    }
    int mx = 0;
    for(int y = 0; y <= n; y++){
        memset(f, 0, sizeof(f));
        for(int dis = 3; dis <= n + 1; dis++){
            for(int i = 1; i + dis - 1 <= n + 1 + y; i++){
                int j = i + dis - 1;
                for(int k = i + 1; k <= j - 1; k++){
                    f[i][j] = max(f[i][j], a[i] * a[k] * a[j] + f[i][k] + f[k][j]);
                }
            }
        }
        mx = max(mx, f[1 + y][n + 1 + y]);
    }
    printf("%d ", mx);
}

P1880 [NOI1995] 石子合并

经典题，但是有环，和上一题同样的处理方式。

测试数据好像不咋大，所以懒得用前缀和去优化最内层那个循环了，直接循环相加，也能AC

#include<bits/stdc++.h>
using namespace std;

const int N = 300;
int nums[N];
int fx[N][N];
int fn[N][N];

int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>nums[i];
        nums[i + n] = nums[i];
    }
    int ans_min = 1e8, ans_max = -1;
    for(int lk = 0; lk <= n; lk++){
        for(int len = 2; len <= n; len++){
            for(int i = 1 + lk; i + len - 1 <= n + lk; i++){
                int j = i + len - 1;
                fx[i][j] = -1;
                fn[i][j] = 1e8;
                for(int k = i; k < j; k++){
                    int sum = 0;
                    for(int z = i; z <= j; z++){
                        sum += nums[z];
                    }
                    fn[i][j] = min(fn[i][j], fn[i][k] + fn[k + 1][j] + sum);
                    fx[i][j] = max(fx[i][j], fx[i][k] + fx[k + 1][j] + sum);
                }
            }
        }
        ans_min = min(fn[1 + lk][n + lk], ans_min);
        ans_max = max(fx[1 + lk][n + lk], ans_max);
    }
    printf("%d\n", ans_min);
    printf("%d", ans_max);
}

P1064 [NOIP2006 提高组] 金明的预算方案

分组背包。

直接套01背包的板子，但是在里面处理的时候要考虑拿0,1,2三种附件的选法，取最大值。

只要是需要同时考虑选取的都可以通过在内层循环里取max的方式去实现。

最开始理解错题了，还以为那个对于的主件是直接第n个主件，结果是第n行hhhhh....所以WA了两次，还在考虑是不是因为附件大小顺序的问题，然后注释里写了个没用的排序，可以忽略。

#include<bits/stdc++.h>
using namespace std;

const int N = 100;
struct Goods{
    int v,w;

    bool operator<(Goods b){
        return v < b.v;
    }
};

vector<Goods> goods[N];
int n,m;
int f[40000];
int to[N]; 
int cnt = 0;
int ans = 0;

int main(){
    memset(f, 0, sizeof f);
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int v,p,q;
        cin>>v>>p>>q;
        if(q == 0){
            goods[++cnt].push_back({v, v * p});
            to[i] = cnt;
        } else {
            goods[to[q]].push_back({v, v * p});
        }
    }

    for(int i = 1; i <= cnt; i++){
//      sort(goods[i].begin() + 1, goods[i].end());
        for(int j = n; j >= goods[i][0].v; j--){
            f[j] = max(f[j], f[j - goods[i][0].v] + goods[i][0].w);

            for(int k = 1; k < goods[i].size(); k++){
                if(j >= goods[i][k].v + goods[i][0].v)
                    f[j] = max(f[j], f[j - goods[i][k].v - goods[i][0].v] + goods[i][k].w+ goods[i][0].w);
            }
            for(int k = 2; k < goods[i].size(); k++){
                for(int l = 1; l < k; l++){
                    if(j >= goods[i][k].v + goods[i][l].v + goods[i][0].v) 
                        f[j] = max(f[j], f[j - goods[i][k].v - goods[i][l].v - goods[i][0].v] + goods[i][k].w + goods[i][l].w + goods[i][0].w);
                }
            }
        }
    }

    for(int i = n; i > 0; i--){
        //printf("%d %d\n", i, f[i]);
        ans = max(f[i], ans);
    }
    printf("%d", ans);
}

P1049 [NOIP2001 普及组] 装箱问题

简单背包。

#include<bits/stdc++.h>
using namespace std;

int p[40];
int f[40];

bool cmp(int a, int b){
    return a>b;
}

int main(){
    int v,n;
    scanf("%d%d", &v, &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &p[i]);
    }
    sort(p + 1, p + 1 + n, cmp);
    memset(f, 0x3f, sizeof(f));
    f[0] = v;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            if(f[j] - p[i] >= 0) f[i] = min(f[j] - p[i], f[i]);
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i = 0; i <= n; i++){
        ans = min(ans, f[i]);
    }
    printf("%d ", ans);
}

P1776 宝物筛选

二进制分组背包

朴素做法是直接把个数拆分为1，这样的话就是一个普通的完全背包，但是这样会超时。

所以正确做法是把每一个宝物的数量划分为二进制数，比如一份有7个的宝物可以划分为1,2,4，这样可以表示从取0-7的所有情况，并且只需要划分为三份，大大节省时间(妙啊)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, W;
int v[N],w[N],m[N];
int f[N];

int main(){
     cin>>n>>W;
     int now = 1;
     for(int i = 1; i <= n; i++){
        int x,y,z;
        scanf("%d%d%d", &x, &y, &z);
        for(int k = 1; k <= z; k *= 2){
            z -= k;
            v[now] = x * k;
            w[now] = y * k;
            now++; 
        }
        if(z > 0){
            v[now] = x * z;
            w[now] = y * z;
            now++;
        }
     }

     for(int i = 1; i < now; i++)
        for(int j = W; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    printf("%d", f[W]);
}

P2725 [USACO3.1]邮票 Stamps

从1开始dp就行了，最开始把所有面值标上1，然后还是从后向前考虑，存的是已经使用的最小数量。

#include<bits/stdc++.h>
using namespace std;

const int N = 300;
int k,n;
int a[N];
int f[5000010];

int main(){
    cin>>k>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        f[a[i]] = 1;
    }
    int p = 1;
    while(f[p] <= k && f[p] != 0){
        for(int i = 1; i <= n && f[p + 1] != 1; i++){
            if(p + 1 - a[i] <= 0) continue;
            if(f[p + 1 - a[i]]){
                if(f[p + 1] == 0){
                    f[p + 1] = f[p + 1 - a[i]] + 1;
                } else {
                    f[p + 1] = min(f[p + 1], f[p + 1 - a[i]] + 1);
                }
            }
        }
        p++;
    }
    printf("%d", p - 1);
}

P1091 [NOIP2004 提高组] 合唱队形

登山(openjudge)

正着反着分别求一次最大上升子序列，然后计算一下最大值，用总数减掉就是答案了

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int zn[N];
int dn[N];
int zf[N];
int df[N];

int dp(int begin, int end, int n){ 
    for(int i = begin; i <= end; i++){
        zf[i] = 1;
        for(int j = begin; j < i; j++){
            if(zn[j] < zn[i]) zf[i] = max(zf[j] + 1, zf[i]);
        }
    }
    for(int i = begin; i <= end; i++){
        df[i] = 1;
        for(int j = begin; j < i; j++){
            if(dn[j] < dn[i]) df[i] = max(df[j] + 1, df[i]);
        }
    }
    int mx = 0;
    for(int i = begin; i <= end; i++){
        mx = max(mx, zf[i] + df[n + 1 - i] - 1);
    }
    return mx;
}

int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>zn[i], dn[n + 1 - i] = zn[i];
    printf("%d", n - dp(1, n, n));

}

P2871 [USACO07DEC]Charm Bracelet S

背包板子，没啥好说，背就完了

#include<bits/stdc++.h>
using namespace std;

const int N = 40000;
int n,m;
int ans = 0;
int w[N], d[N];
int f[N];

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>w[i]>>d[i];
    for(int i = 1; i <= n; i++){
        for(int l = m; l >= w[i]; l--){
            f[l] = max(f[l], f[l - w[i]] + d[i]);
            ans = max(ans, f[l]);
        }
    }
    printf("%d", ans);
}

P2467 [SDOI2010]地精部落

结论题，没想出来，直接开摆。

其实有点像AT的一道dp，当时也没写出来hhhhhh....

贴个题解: https://www.cnblogs.com/ezuyz/p/14720622.html

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int n,p;
ll f[2][5000]; 

int main(){
    cin>>n>>p;
    f[1][0] = 4;
    f[1][1] = 2;

    for(int i = 4; i <= n; i++){
        for(int j = 0; j <= i; j++){
            f[0][j] = f[1][j];
            f[1][j] = 0;
        }
        for(int j = 0; j <= i - 3; j++){
            f[1][j] = (f[1][j] + f[0][j] * 2) % p;
            if(j) f[1][j - 1] = (f[1][j - 1] + f[0][j] * j) % p;
            f[1][j + 1] = (f[1][j + 1] + f[0][j] * (i - 2 - j)) % p;
        }
    }

    printf("%d", f[1][0]);
}

寒假动规专项练习 A-L

目录

P1006 [NOIP2008 提高组] 传纸条

P1052 [NOIP2005 提高组] 过河

P1130 红牌

P1063 [NOIP2006 提高组] 能量项链

P1880 [NOI1995] 石子合并

P1064 [NOIP2006 提高组] 金明的预算方案

P1049 [NOIP2001 普及组] 装箱问题

P1776 宝物筛选

P2725 [USACO3.1]邮票 Stamps

P1091 [NOIP2004 提高组] 合唱队形

P2871 [USACO07DEC]Charm Bracelet S

P2467 [SDOI2010]地精部落

暂无评论

发表评论取消回复

最新文章

寒假动规专项练习 A-L

目录

P1006 [NOIP2008 提高组] 传纸条

P1052 [NOIP2005 提高组] 过河

P1130 红牌

P1063 [NOIP2006 提高组] 能量项链

P1880 [NOI1995] 石子合并

P1064 [NOIP2006 提高组] 金明的预算方案

P1049 [NOIP2001 普及组] 装箱问题

P1776 宝物筛选

P2725 [USACO3.1]邮票 Stamps

P1091 [NOIP2004 提高组] 合唱队形

P2871 [USACO07DEC]Charm Bracelet S

P2467 [SDOI2010]地精部落

暂无评论

发表评论 取消回复

最新文章

发表评论取消回复