DQS DQS

HIT Summer Training Day3 简单DP

in 简单DP,算法,DP,模拟赛read (197) 文章转载请注明来源!

今天是一些很简单的DP,几乎都是看完题出结果……我老是写挂什么鬼……

以后还是要提高姿势水平。


A : poj - 2533

LIS问题。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int a[SZ],n,f[SZ];

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]),f[i] = INF;
    for(int i = 1;i <= n;i ++)
        *lower_bound(f + 1,f + 1 + i,a[i]) = a[i];
    printf("%d\n",lower_bound(f + 1,f + 1 + n,INF) - f - 1);
    return 0;
}


B : poj - 1163

数字三角形。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 5010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int a[SZ][SZ],n;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= i;j ++)
            scanf("%d",&a[i][j]);
    for(int i = n - 1;i >= 1;i --)
        for(int j = 1;j <= i;j ++)
            a[i][j] += max(a[i + 1][j],a[i + 1][j + 1]);
    printf("%d\n",a[1][1]);
    return 0;
}


C : poj - 2250

LCS问题。

多组数据,每组给两个文本,每个文本由好多单词构成。以每个单词为一个元素,输出这两个文本构成的最长子序列。

dfs输出方案。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 510;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

string a[SZ],b[SZ],ans[SZ];
int f[SZ][SZ],n,m;
char s[SZ];

struct haha
{
    int x,y;
}pre[SZ][SZ];

void dfs(int x,int y,int d)
{
    if(d > f[n][m] || x < 1 || y < 1) return ;
    //cout << x << " " << y << " " << d << " " << a[x] << " " << b[y] << endl;
    if(a[x] == b[y]) ans[++ d] = a[x];
    int nx = pre[x][y].x,ny = pre[x][y].y;
    dfs(nx,ny,d);
}

int main()
{
    while(~scanf("%s",s))
    {
        n = 0,m = 0;
        while(s[0] != '#')
        {
            a[++ n] = s;
            scanf("%s",s);
        }
        scanf("%s",s);
        while(s[0] != '#')
        {
            b[++ m] = s;
            scanf("%s",s);
        }
        memset(f,0,sizeof(f));
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                if(a[i] == b[j])
                {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    pre[i][j] = (haha){i - 1,j - 1};
                }
                else
                {
                    haha x;
                    if(f[i - 1][j] > f[i][j - 1])
                        x = (haha){i - 1,j};
                    else
                        x = (haha){i,j - 1};
                    f[i][j] = max(f[i - 1][j],f[i][j - 1]);
                    pre[i][j] = x;
                }
        dfs(n,m,0);
        for(int i = f[n][m];i >= 1;i --)
            cout << ans[i] << " "; puts("");
            //printf("%d\n",f[n][m]);
    }
    return 0;
}


D : poj - 3624

01背包。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 1000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int w[SZ],v[SZ],n,m;
int f[SZ];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
        scanf("%d%d",&w[i],&v[i]);
    for(int i = 1;i <= n;i ++)
        for(int j = m;j >= w[i];j --)
            f[j] = max(f[j],f[j - w[i]] + v[i]);
    printf("%d\n",f[m]);
    return 0;
}


E : poj - 1231

这个题据说出题人放错了…算了不写了。


F : codeforces - 544C

n个程序员写m行代码,第i个程序员每写一行代码出$a_i$个bug,要求总bug数要小于等于k。求总方案数模mod。

把行数和bug数看做二维费用,发现是完全背包问题。

注意赋初值:行数要求正好m行,bug数要求小于等于k即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 510;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int f[SZ][SZ],n,m,K,a[SZ],mod;


int main()
{
    scanf("%d%d%d%d",&n,&m,&K,&mod);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    for(int i = 0;i <= K;i ++)
        f[0][i] = 1;
/*    for(int i = 1;i <= n;i ++)
        for(int k = 0;k <= K;k ++)
            for(int j = 0;j <= m;j ++)
                for(int s = j - k / a[i];s <= j;s ++)
                    f[i][j][k] += f[i - 1][s][k - (j - s) * a[i]];*/
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            for(int k = a[i];k <= K;k ++)
                f[j][k] = (f[j][k] + f[j - 1][k - a[i]]) % mod;
    printf("%d\n",f[m][K]);
    return 0;
}


G : codeforces - 106C

题目很繁琐…

总之就是可以算出每个物品最多可以取得次数和价值,然后就是多重背包了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 1000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int w[SZ],v[SZ],t[SZ],n,m;
int f[SZ];

void work1(int w,int v)
{
    for(int j = m;j >= w;j --)
        f[j] = max(f[j],f[j - w] + v);
}

void work2(int w,int v)
{
    for(int j = w;j <= m;j ++)
        f[j] = max(f[j],f[j - w] + v);
}

void work3(int w,int v,int t)
{
//    cout << w << " " << v << " " << t << endl;
    if(w * t >= m) { work2(w,v); return ;}
    int x = 1;
    while(x <= t)
    {
        work1(w * x,v * x);
        t -= x;
        x <<= 1;
    }
    work1(w * t,v * t);
}

int a[SZ],b[SZ],c[SZ],d[SZ];

int main()
{
    int c0,d0;
    scanf("%d%d%d%d",&m,&n,&c0,&d0);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
        w[i] = c[i];
        t[i] = a[i] / b[i];
        v[i] = d[i];
    }
    n ++;
    w[n] = c0,t[n] = m / c0,v[n] = d0;
    for(int i = 1;i <= n;i ++)
        work3(w[i],v[i],t[i]);
    printf("%d\n",f[m]);
    return 0;
}

H : codeforces - 148E

给n个架子,每个架子上至多有100个物品,从左到右依次排开,每个物品有一个价值。要求选取m个物品使得物品总价值最大。

选取物品规则:对于一个架子,只能选取当前架子上最左边、最右边的物品,选择后移除。

对于每一行计算v[i]表示取i个物品的最大价值,v[i]可以用前缀和和后缀和取max。不能贪心。

然后就是分组背包问题。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int SZ = 100010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int g[SZ][105];
int f[SZ],v[SZ],n,m;

int dp[SZ],s1[SZ],s2[SZ];

void calc(int a[])
{
    for(int i = 1;i <= a[0];i ++)
        s1[i] = s1[i - 1] + a[i];
    for(int i = 1;i <= a[0];i ++)
        s2[i] = s2[i - 1] + a[a[0] - i + 1];
    for(int i = 1;i <= a[0];i ++)
    {
        v[i] = 0;
        for(int j = 0;j <= i;j ++)
            v[i] = max(v[i],s1[j] + s2[i - j]);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&g[i][0]);
        for(int j = 1;j <= g[i][0];j ++)
            scanf("%d",&g[i][j]);
    }

    for(int i = 1;i <= n;i ++)
    {
        calc(g[i]);
        for(int j = m;j >= 0;j --)
        {
            for(int k = max(0,j - g[i][0]);k <= j;k ++)
                f[j] = max(f[j],f[k] + v[j - k]);
        }
    }
    printf("%d\n",f[m]);
    return 0;
}


I : codeforces - 366C

给出a[i]和b[i],要求选出k个使得$\frac{\sum a_i}{\sum b_i}= k$,并且要求$\sum a_i$最大。

容易发现其实是要求选出k个使$\sum (a_i-k*b_i)=0$。发现这个东西的范围有限,可以放到状态里。

$f_{i,j}$表示前i个,当前之和是j的最大$a_i$。

注意初始只有$f_{0,0}$合法。答案是$f_{n,k}$

发现第二维可能是负的,于是统一加一个大数。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

const int SZ = 110010;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int a[SZ],b[SZ],c[SZ],n,m;

int f[102][SZ];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)  scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++)  scanf("%d",&b[i]);
    for(int i = 1;i <= n;i ++)  c[i] = a[i] - b[i] * m;//cout << c[i] << " "; puts("");
    for(int i = 0;i <= n;i ++)
        for(int j = 0;j <= 110000;j ++)
            f[i][j] = -INF;
    f[0][10000] = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = 0;j <= 110000;j ++)
            if(j - c[i] >= 0)
                f[i][j] = max(f[i - 1][j],f[i - 1][j - c[i]] + a[i]);
            else
                f[i][j] = f[i - 1][j];

/*    for(int i = 1;i <= n;i ++,puts(""))
        for(int j = 990;j <= 1010;j ++)
            printf("%5d",f[i][j]);
*/
    int ans = f[n][10000] <= 0 ? -1 : f[n][10000];
    printf("%d\n",ans);
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

简单DP算法DP模拟赛
最后由DQS修改于2017-08-06 02:42
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆