SCAU ACM校队寒训题 DP专题

专题"/>

SCAU ACM校队寒训题 DP专题

A - String Partition

动态规划思想：
1.外层循环遍历下标，内层循环遍历一遍当前下标前十个数（int大小就是10位）。

2.dp[i]就表示当前下标下的sum最大值，那么内层循环就相当于是“分割”，把i之前的元素切成左右两部分，dp[j-1]部分及j-i部分，后者就是要额外算的，而前面j-1部分因为已经遍历过了所以已经是存好的。

3.不妨设j-i部分的数合并起来后为sum，那么我只用取内层循环里面dp[j-1]+sum的最大值即可了。

状态转移方程：

dp[i] = max((int)sum+(j-1<0?0:dp[j-1]), dp[i]) 。

4.最后的dp[s.size()-1]即是答案。

#include <iostream>
#include <cstdio>
#include <limits.h>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dp[200+5];
int main()
{int kase;cin>>kase;while(kase--){string s;cin>>s;dp[0] = s[0] - '0';for(int i=1;i<s.size();i++){dp[i] = 0;for(int j=i;j>=i-9&&j>=0;j--){ll  sum = 0;for(int k=j;k<=i;k++){sum*=10;sum+=(s[k]-'0');}if(sum<=INT_MAX)dp[i] = max((int)sum+(j-1<0?0:dp[j-1]), dp[i]);}}cout<<dp[s.size()-1]<<endl;}return 0;
}

B - Is Bigger Smarter?

动态规划思路：
1.一看完题目，就感觉这纯粹是最长上升子序列的变种题，若固定了体重或智商某一个的排序方式，那么另一个就只要严格反过来就行了。

2.我这里把体重降序排列，即求智商的最长上升子序列。
3.上述步骤要写在结构体里面，因为最后输出的位置只和初始位置有关，结构体里面专门拿一个pos变量存序号。排序即是对结构体排序。

4.最长上升子序列的核心代码也很简单，dp[i]存当前最优解，内层j循环用来找智商比i位置小的，而且dp[j]要最大的即可。

5.唯一和最长上升子序列例题不一样就是要找出序列内包含的元素，这和背包问题中找出背包内物品的方法一样，倒序循环，找到一个dp值比当前小1而且智商还小的就是了，同时更新当前dp值和智商。

#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
struct  data{int pos;int w;int iq;
};
struct data a[1000000];
int dp[1000000];
bool cmp(struct data a, struct data b)
{return a.w>b.w;
}
int main()
{int n , m;int p = 1;while(scanf("%d%d",&n,&m)!=EOF){a[p-1].pos=p;a[p-1].w=n;a[p-1].iq=m;p++;}sort(a,a+p-1,cmp);for(int i=0;i<p-1;i++){dp[i] = 1;int max1=0;for(int j=0;j<i;j++){if(dp[j]>max1&&a[i].iq>a[j].iq)max1 = dp[j];}dp[i] = max1 + 1;}int obj =0;int max1=0;for(int i=0;i<p-1;i++){if(dp[i]>max1){max1 = dp[i];obj = i;}}if(max1==1){cout<<0<<endl;}else{cout<<max1<<endl;cout<<a[obj].pos<<endl;int cur_num = max1;int cur_index=obj;for(int i=obj-1;i>=0;i--){if(dp[i]==cur_num-1&&a[i].iq<a[cur_index].iq){cout<<a[i].pos<<endl;cur_num --;cur_index = i;}}}return 0;
}

C - Dividing coins

动态规划思路：
1.类似于天平问题，转化为一个人尽可能地拿到贴近sum/2的硬币量。

2.先将dp数组初始化为0，这时候“0”就代表这个位置是没有硬币来填充的，换句话说，凑不到这么多钱。

3.然后就是动态规划的主体，外层循环控制n个硬币的遍历，内层就是sum/2到a[i]的轮番填充dp，代表可以通过硬币a[i]凑到j元，即是dp[j]=dp[j-a[i]]+a[i]，这时候dp为零的地方，便“恰好”能表示不能与a[i]相加得到j，硬币a[i]来凑j只能到a[i]那么多了。然后只需要将每次得到的dp[j]取最大就行了（最大也不会超过sum/2）。

补充：dp[i]表示以当前硬币能凑到最贴近i的数量。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
int dp[500000+5];int main()
{int kase;cin>>kase;while(kase--){memset(dp,0,sizeof(dp));int n;cin>>n;int sum=0;vector<int >  a;for(int i=0;i<n;i++){int t;cin>>t;a.push_back(t);sum+=a[i];}sort(a.begin(),a.end());//dp[0] = 0;int  t =sum/2;for(int i=0;i<n;i++){for(int j=t;j>=a[i];j--){  //因为是硬币只能用一次，要从大到小遍历，若从小到大遍历，会出现多次利用a[i]的可能。dp[j]=max(dp[j],dp[j-a[i]]+a[i]);}}cout<<(sum-2*dp[t])<<endl;}return 0;
}

D - Optimal Array Multiplication Sequence

一开始题意理解了半天，其实就是问区间内连续乘积的最小值。但是想了很久后还是不知道怎么实现，最后看了题解后才明白。

动态规划思路：
1.第一层循环用来控制连续区间的长度。

2.第二层循环用来控制区间左右端点的移动，每次向后挪动1个单位。

3.第三层循环用来控制该区间的最优解，循环下标k遍历区间内部的元素，k代表以k位置为分隔点，将区间分成左右两部分。最优解从区间内部max（dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]）中取得，p数组用来存当前元素的左右端点。详见代码注释。

路径记录及输出思路：
1.在上述第三层循环中，每次更新最优解，都用数组d[i][j]记录一下k，代表k是i-j区间内的分割点。
2.然后输出的时候以print(l,r)函数，l,r分别是区间左右端点，内部只需要不断递归调用print（l,d[i][j]）和print(d[i][j]+1,r)就行了。递归出口就是l大于等于r时。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=100;int n;
int p[maxn];
int dp[maxn][maxn];
int d[maxn][maxn];void DP()
{for(int len=2; len <= n; ++len)         //外层遍历一遍从第三个元素开始的循环{for(int i=1,j=i+len-1; j <= n; ++i,++j)     //在每次长度更新的同时更新区间长度，每次查找区间长度为len时{//   cout <<i<<' '<<j<<endl;for(int k=i; k < j; ++k)                 //   i到j区间内的最优解     -> 找出是否被k分隔{int cur=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];     //若以k为分界，那么当前的权值就是区间i-k和区间k+1到j的权值和，再加上左边区间的右连续端点*自身的右端点*右区间的左连续端点if(dp[i][j] > cur){d[i][j]=k;       //d用来记录k位置是用来分隔左右区间的dp[i][j]=cur;}}}}
}
void Print(int l,int r)
{if(l == r){printf("A%d",l);return ;}if(l > r)return ;printf("(");Print(l,d[l][r]);// [l,r]在d[l][r]处分割printf(" x ");          //前后递归调用，知道找到某一个独立分割点Print(d[l][r]+1,r);printf(")");
}
void Solve()
{for(int i=0; i <= n; ++i)for(int j=0; j <= n; ++j)dp[i][j]=(i == j ? 0:INF);DP();Print(1,n);printf("\n");
}
int main()
{int kase=1; while(~scanf("%d",&n) && n){for(int i=1; i <= n; ++i)  //第i个矩阵的行和列为p[i-1],p[i]{int a,b;scanf("%d%d",&a,&b);p[i-1]=a;p[i]=b;}printf("Case %d: ",kase++);Solve();}return 0;
}

E - The Tower of Babylon

和前面的B题一个模子刻出来的，最长上升子序列，只是把问最长改成了最大z（高度）值，直接一次提交秒了。
动态规划思路：
1.题目也说了给的长方体可以随意变换基底，怎么拼接都行，那么其实题目给了你一组长方体数据，相当于给了你三个（xyz严格按照长宽高顺序）。那么我先将输入数据存到tmp[3]数组中，排序一下，然后把最大的两个值给x（长）（因为基底长一定比宽大，好像是废话），其他两个组合成宽和高，注意长选择第二大的时候宽一定要是最小的那个。以上变量以结构体形式存储

2.对结构体以x进行将序排列。

3.然后就是最长上升子序列的核心代码了，因为x已经是降序的了，因为dp[i]代表当前要放到能放到的最高处，那么只要控制宽也严格单调递减就行了。只需要加多两句话，长度相同时continue以及max用来存储最大高度，dp[i] = max + 当前i高度。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;typedef struct rectangular{int x;int y;int z;
}rec;bool cmp(rec a, rec b)
{return a.x>b.x;
}int dp[900000];
rec  a[900000];
int main()
{int n;int kase = 1;while(~scanf("%d",&n)&&n){int tmp[3];for(int i=0;i<n*3;i+=3){cin>>tmp[0]>>tmp[1]>>tmp[2];sort(tmp,tmp+3);a[i].x = tmp[2];a[i].y = tmp[1];a[i].z = tmp[0];a[i+1].x = tmp[2];a[i+1].z = tmp[1];a[i+1].y = tmp[0];a[i+2].x = tmp[1];a[i+2].y = tmp[0];a[i+2].z = tmp[2];}/*for(int i=0;i<n*3;i++)cout<<a[i].x<<' '<<a[i].y<<' '<<a[i].z<<endl;*/sort(a,a+3*n,cmp);dp[0] = a[0].z;for(int i=1;i<3*n;i++){int max = 0;for(int j=0;j<i;j++){if(a[j].x==a[i].x)  continue;if(dp[j]>max&&a[j].y>a[i].y)max = dp[j];}dp[i] = max + a[i].z;}int res=0;for(int i=1;i<3*n;i++){if(dp[i]>res)res = dp[i];}printf("Case %d: maximum height = %d\n",kase++,res);}return 0;
}

F - Bachet’s Game

简单的博弈题
动态规划思想：
1.比如题给数据20 3 1 3 8
我想让S赢，那么就说明我能用1 3 8凑到20，最后一步肯定也是加上这三个数才得到20的，换句话说，最后一步，肯定是已经拿走了19个，或者 17个 ，或者12个石子，才能让S最后一步拿那三颗反杀的。

2.那么这些19,17，12怎么来的呢？是不是又是由这三颗石子组成的？以此类推，状态转移方程就出来了。当前dp[i]要最优，dp[i-a[j]]一定要已经是走过的。

3.可能你觉得已经结束了，但是这毕竟是回合制游戏，上一步要同时满足用当前石子凑得到，还要满足是另一个人帮你凑好的，这样才能使得“当前这一步轮到你”。其实也很简单，多开一个数组win，看上一步如果是可行（1）的话，当前这一步其实是另外一个人走的，那么当前win[i]就是0，而dp[i]用来判别当前石子数量能不能凑到。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int dp[1000000+5];
int  a[1000000+5];
int win[1000000+5];
int main()
{int n;while(~scanf("%d",&n)&&n){//  memset(dp,0,sizeof(dp));int m;cin>>m;for(int i=0;i<m;i++){cin>>a[i];}for(int i=0;i<=n;i++){dp[i] = 0;win[i] = 0;for(int j=0;j<m;j++){if(a[j]==i){dp[i] = 1;win[i] = 1;break;}if(dp[i-a[j]]){if(win[i-a[j]])win[i] = 0;elsewin[i] = 1;dp[i] = 1;if(win[i]==1)  break;}}}if(dp[n]&&win[n]){cout<<"Stan wins"<<endl;}elsecout<<"Ollie wins"<<endl;}return 0;
}

G - Walking on the Safe Side

最典型的走格子问题，也是最简单的一类。
动态规划思路：
1.将不能走的位置dp[i][j]标记为0即可。
2.然后进行状态转移 ( dp[i][j] = dp[i-1][j] + dp[i][j-1] )就完事了。
这道题恶心一点的地方就是它的输入输出格式了，被坑了两次。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int dp[5000][5000];
int a[5000][5000];
int main()
{int kase;cin>>kase;while(kase--){int row , col;cin>>row>>col;for(int i=0;i<row;i++)for(int j=0;j<col;j++){a[i][j] = 0;dp[i][j] = 0;}for(int i=0;i<row;i++){int tmp;cin>>tmp;string s;getline(cin,s);int sum=0;