关于取数的题目（区间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
题目描述
给定两个长度为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;
} 题目描述：
设有 𝑛 × 𝑚 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，
求它能取到的整数之和的最大值。
题解：
这题和上一道题目类似，只是多了一种情况，可以向上走，同时也只走一遍。
开始的时候我的思路是从上往下，从左往右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;
} 