关于取数的题目(区间dp)

关于取数的题目(区间dp)

首先我们来看一道简单的取数问题:

取数游戏:有三个数字,把他们组成一个最大的三位数,暴力就行了
代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const ll INF = -1e9;
const ll N =80+7;
const ll mod = 9999999967;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
int main(){
    int a,b,c,t;
    cin>>t;
    while(t--){
        cin>>a>>b>>c;
        if(a<b) swap(a,b);
        if(a<c) swap(a,c);
        if(b<c) swap(b,c);
        printf("%d%d%d\n",a,b,c);
    }

}

取数游戏

接下来的就是dp的题目了:

取数游戏2

取数游戏2

题目描述

给定两个长度为n的整数列A和B,每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax,则第i次取走的数的价值vi=bi⋅ax,现在希望你求出∑vi的最大值。

题解:

这是一道区间dp问题,dp[i][j]代表左边取i个,右边取j个能获得的最大价值
显然有递推式:dp[i][j]=max(dp[i-1][j]+a[i]b[i+j],dp[i][j-1]+a[n-j+1]b[i+j])

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+7;
const ll MOD = 1e9 + 7;
int a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(dp,0,sizeof(dp));
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];

        for(int i=1;i<=n;i++){
            dp[i][0]=dp[i-1][0]+a[i]*b[i];//左边取i-1个,右边取0个
            dp[0][i]=dp[0][i-1]+a[n-i+1]*b[i];
        }//因为下面是从左右都取一个开始递推
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=max(dp[i-1][j]+a[i]*b[i+j],dp[i][j-1]+a[n-j+1]*b[i+j]);
                if(i+j==n) ans=max(ans,dp[i][j]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

矩阵取数游戏

题目描述:

对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:

1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;

2.每次取走的各个元素只能是该元素所在行的行首或行尾;

3.每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值 * 2i,其中i表示第i次取数(从1开始编号);

4.游戏结束总得分为m次取数得分之和。

题解:

其实这道题目就相当于取数游戏2的加强版,因为每行取数的结果互不影响。需要注意的是会爆long long ,需要开_int128_t,
递推式:
dp[k][i][j]=max(dp[k][i-1][j]+a[k][i]qpow(2,i+j),dp[k][i][j-1]+a[k][m-j+1]qpow(2,i+j))

代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef  __int128_t ll;
const ll INF = -1e9;
const ll N =80+7;
const ll mod = 9999999967;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
inline void print(ll x){
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
ll dp[N][N][N], a[N][N];
ll ans[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    a[i][j]=read();
    for(int k=1;k<=n;k++)
        for(int i=1;i<=m;i++){
            dp[k][i][0]=dp[k][i-1][0]+a[k][i]*qpow(2,i);
            dp[k][0][i]=dp[k][0][i-1]+a[k][m-i+1]*qpow(2,i);
        }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                dp[k][i][j]=max(dp[k][i-1][j]+a[k][i]*qpow(2,i+j),dp[k][i][j-1]+a[k][m-j+1]*qpow(2,i+j));
                if(i+j==m) ans[k]=max(ans[k],dp[k][i][j]);
            }
        }
    }
  ll sum=0;
   for(int i=1;i<=n;i++) sum+=ans[i];
   print(sum);

}

方格取数

题目描述:

给你一个n*n的方格,每个位置都有一个数字(正整数或者0),有个人从起点(1,1)开始走到终点(n,n),他只能向下或者向右走,走过每个有正整数方格都可以选择是否拿走那个正整数(注意,拿走正整数后那个方格的数字变成0),题目要你求这个人走两遍方格能拿走的最大数字和。

题解:

可以看成是两个人同时从起点往终点走

两个人在同一个位置的时候:dp[i][j][k][p]=max(max(dp[i-1][j][k-1][p],dp[i-1][j][k][p-1]),max(dp[i][j-1][k-1][p],dp[i][j-1][k][p-1]))+a[i][j]
两个人不在同一个位置的时候:dp[i][j][k][p]=max(max(dp[i-1][j][k-1][p],dp[i-1][j][k][p-1]),max(dp[i][j-1][k-1][p],dp[i][j-1][k][p-1]))+a[i][j]+a[k][p]

代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 15;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
int a[N][N],dp[N][N][N][N];
int  main()
{
    int n;
    cin>>n;
    int x,y,z;
    while(cin>>x>>y>>z){
        if(x==0&&y==0&&z==0)
        break;
        a[x][y]=z;
    }
    dp[1][1][1][1]=a[1][1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                for(int p=1;p<=n;p++)
                    if(i==k&&j==p){
                        dp[i][j][k][p]=max(max(dp[i-1][j][k-1][p],dp[i-1][j][k][p-1]),max(dp[i][j-1][k-1][p],dp[i][j-1][k][p-1]))+a[i][j];
                    }
                    else dp[i][j][k][p]=max(max(dp[i-1][j][k-1][p],dp[i-1][j][k][p-1]),max(dp[i][j-1][k-1][p],dp[i][j-1][k][p-1]))+a[i][j]+a[k][p];
    cout<<dp[n][n][n][n]<<endl;
}

方格取数(number)

题目描述:

设有 𝑛 × 𝑚 的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中的整数,
求它能取到的整数之和的最大值。

题解:

这题和上一道题目类似,只是多了一种情况,可以向上走,同时也只走一遍。

开始的时候我的思路是从上往下,从左往右dp遍历,但是发现了只能考虑到向下,向右的情况,然后错了,之后看了别人的代码,用了两个数组,一个存向下,向右的方案,一个存向上向右的方案,比较更优的解即可。

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const ll INF = -1e9;
const ll NUM =1e4+7;
const ll mod = 9999999967;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
int g[NUM][NUM],f[NUM][NUM],a[NUM][NUM];
int main(){
    int n,m;
       cin>>n>>m;
       for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
            cin>>a[i][j];
       for(int i=0;i<=n+1;i++)
       for(int j=0;j<=m+1;j++)
              g[i][j]=f[i][j]=INF;
       f[1][1]=a[1][1];
       for(int j=1;j<=m;j++){
           for(int i=1;i<=n;i++) g[i][j]=f[i][j]=max(f[i][j],f[i][j-1]+a[i][j]);//往右走
           for(int i=1;i<=n;i++) f[i][j]=max(f[i][j],f[i-1][j]+a[i][j]);//往下走
           for(int i=n;i>=1;i--) g[i][j]=max(g[i][j],g[i+1][j]+a[i][j]);//往上走
           for(int i=1;i<=n;i++) f[i][j]=max(g[i][j],f[i][j]);
       }
       cout<<f[n][m]<<endl;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-09 21:15
清华大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-30 20:45
门头沟学院_2023
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议