Photo by Suvan Chowdhury from Pexels
HDU1024 Max Sum Plus Plus
题意是说，对于一个序列\(S\)，找出\(m\)个数对\((i_1,j_1)\)，\((i_2,j_2)\)，\((i_3,j_3)\)，······,\((i_m,j_m)\)，使得这些数对对应的区间和的和最大，也就是让\(Sum=sum(i_1,j_1)+sum(i_2,j_2)+sum(i_3,j_3)+...+sum(i_m,j_m)\)最大。输出该最大和。
首先，状态转移方程为 \[ dp[i][j]=max(dp[i][j-1]+arr[j],max(dp[i-1][k])+arr[j])\\ 0<k<j \] \(dp[i][j]\)表示将前\(j\)个数分成\(i\)组，\(dp[i][j-1]+arr[j]\)表示前j个数分成\(i\)组，第\(j\)个数放在第\(i\)组里面；\(max(dp[i-1][k])+arr[j]\)表示从前\(j-1\)个数中取出\(k\)个数，将他们分成\(i-1\)组，然后第\(j\)个数自成一组，总共\(i\)组。
但如果只是单纯这样做的话，由于数据范围比较大\((1 ≤ x ≤ n ≤ 1000000)\)，这种\(O(n^3)\)的做法肯定会超时，因此要做一定的优化。
方法是，另外开一个\(maxi\_[]\)数组，用来存放\(dp[i-1]\)中的最大值。\(maxi\_[j-1]\)标识的就是当前\(dp[i-1]\)中的最大值。
代码如下：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug cout<<"debug"<<endl;
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define IOS std::ios::sync_with_stdio(false)
typedef long long ll;
const int maxn=1e6+5;
using namespace std;
int arr[maxn];
int dp[maxn];
int maxi_[maxn];
int main()
{
int m,n;
while(scanf("%d %d",&m,&n)!=EOF){
int ans=-INF;
mst(dp,0);mst(maxi_,0);
mst(arr,0);
for(int i=1;i<=n;i++)
scanf("%d",&arr[i]);
for(int i=1;i<=m;i++){
ans=-INF;
for(int j=i;j<=n;j++){
dp[j]=max(dp[j-1]+arr[j],maxi_[j-1]+arr[j]);
maxi_[j-1]=ans;
ans=max(ans,dp[j]);
}
}
printf("%d\n",ans);
}
return 0;
}HDU1029 lgnatius and the Princess IV
题意是说，给出一个奇数N，以及一个长度为N的整数序列，问序列中出现次数至少为\(\frac{N+1}{2}\)的数是什么
- 可以直接用map做
- 但既然是dp专题，肯定要用dp来做🦆
dp做法涉及到了一个叫做摩尔投票算法的东西。事实上这道题就是该算法的板子题。下面先上代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug cout<<"debug"<<endl;
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define IOS std::ios::sync_with_stdio(false)
typedef long long ll;
const int maxn=1e6+5;
using namespace std;
int arr[maxn];
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
scanf("%d",&arr[i]);
int cnt=0;int ans;
for(int i=1;i<=n;i++){
if(cnt==0){
ans=arr[i];
cnt++;
}else{
if(ans==arr[i])
cnt++;
else
cnt--;
}
}
printf("%d\n",ans);
}
return 0;
}有一种非常通俗易懂的方法解释该算法：将每一种数想象成是一个阵营的士兵，当一个阵营的士兵遇到另一个阵营的士兵时，双方会发生战斗，且结果一定是同归于尽。\(cnt\)其实就是在统计一个阵营的士兵数目。当所有士兵都战斗过一次后（也就是序列被遍历完了），剩下的士兵就是我们要求的数。
HDU1069 Monkey and Banana
题目大意是说，有若干种方块，对于每一种方块，可以以它的任意一个面为底面。现在要求使用这若干种方块堆成一座塔，要求是每一个方块正上方的那个方块的底面长和宽必须严格小于当前方块顶面的长和宽。
emmmmmmmm这题就是Uva的那道巴比伦塔啊......就改了一下题目描述，连样例都没改hhhhh。
做法就是求DAG上的最长路，dfs+记忆化即可。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=20005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int bs[35][5];
int dp[35][5];
int n;
void get_(int arr[],int idx,int hidx)
{
int cnt=0;
for(int j=1;j<=3;j++){
if(j!=hidx){
arr[cnt++]=bs[idx][j];
}
}
}
int solve(int idx,int hidx)
{
int& ans=dp[idx][hidx];
if(ans!=-1)
return ans;
ans=0;
int b1[2],b2[2];
get_(b1,idx,hidx);
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
get_(b2,i,j);
if((b2[0]<b1[0]&&b2[1]<b1[1])||(b2[1]<b1[0]&&b2[0]<b1[1]))
ans=max(ans,solve(i,j));
}
}
ans+=bs[idx][hidx];
return ans;
}
int main()
{
IOS;
int kase=0;
while(cin>>n&&n){
mst(bs,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
cin>>bs[i][j];
}
sort(bs[i]+1,bs[i]+4);
}
mst(dp,-1);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
ans=max(ans,solve(i,j));
}
}
cout<<"Case "<<++kase<<": maximum height = "<<ans<<endl;
//Case 1: maximum height = 40
}
return 0;
}HDU1074 Doing Homework
一道状压dp的题目，刚看到题目的时候真的没有想到是状压dp......因为当时我还不会状压......看了题解，才知道这题要用状压。于是去学了一波，做了几道入门题，然后才来做这道题。
这题的题解已经在之前的一篇文章中有写到了，故贴出链接，不再赘述
HDU1087 Super Jumping! Jumping! Jumping!
其实就是求最大和上升子序列，也就是对于给定的序列，找出一个子序列，使得该子序列的总和最大。输出该最大和。
状态转移方程为: \[ dp[i]=max(dp[j]+arr[i],dp[i]),\ 0 ≤j<i \] \(dp[i]\)表示由前\(i\)个数组成的序列的最大和上升子序列和为多少。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int arr[1005];
int dp[1005];
int main()
{
IOS;
int n;
while(cin>>n&&n){
mst(arr,0);mst(dp,-INF);
for(int i=1;i<=n;i++)
cin>>arr[i];
int ans=0;
dp[1]=arr[1];
for(int i=2;i<=n;i++){
dp[i]=arr[i];
for(int j=0;j<i;j++){
if(arr[j]<arr[i]){
dp[i]=max(dp[i],dp[j]+arr[i]);
}
}
}
for(int i=1;i<=n;i++)
ans=max(dp[i],ans);
cout<<ans<<endl;
}
return 0;
} HDU1114 Piggy-Bank
完全背包模板题，之前的题解中已有提及到此题，不在赘述。
HDU1176 免费馅饼
题意是说，有若干个馅饼掉落，馅饼\(p_i\)会在时间\(t_i\)掉落到位置\(x_i\)处。初始时你位于位置5，每秒钟你只可以往左或往右移动一个单位，问能够接到的馅饼数目是多少。 \[ dp[i][j]=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]))+bs[i][j] \] \(dp[i][j]\)表示在时间\(i\)、位置\(j\)接到的最多馅饼数；\(bs[i][j]\)表示在时间\(i\)，位置\(j\)掉到地上的馅饼的数目。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=100000+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int bs[maxn][15]; //时间,位置
int dp[maxn][15]; //时间,位置
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n){
int ubt=-INF;mst(bs,0);
for(int i=1;i<=n;i++){
int x,t;
scanf("%d %d",&x,&t);
bs[t][x]++;
ubt=max(ubt,t);
}
mst(dp,0);
for(int i=ubt;i>=0;i--){
for(int j=0;j<=10;j++){
dp[i][j]=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]))+bs[i][j];
}
}
int ans=dp[0][5];
cout<<ans<<endl;
}
return 0;
}HDU1260 Tickets
题意是说，对于一个整数序列，有两种操作，一种是删除当前的一个数，一种是删除相邻的两个数，两种操作都对应一定的费用。现在要求从左到右进行操作，问将所有数删除掉所需要的最小费用是多少。
直接转移即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=2005;
int t1[maxn],t2[maxn];
int dp[maxn];
void Time(int todo)
{
int tmp=todo;
int mins=todo/60;
int hr=8+mins/60;
int sec=todo%60%60;
mins%=60;
int htmp=hr;
if(hr>12) hr-=12;
printf("%02d:%02d:%02d ",hr,mins,sec);
if(htmp<12) printf("am\n");
else printf("pm\n");
}
int main()
{
int n,k;
scanf("%d",&n);
while(n--)
{
memset(dp,0,sizeof(dp));
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
scanf("%d",&k);
for(int i=1;i<=k;i++) scanf("%d",&t1[i]);
for(int i=1;i<=k-1;i++) scanf("%d",&t2[i]);
dp[1]=t1[1];
dp[2]=min(t1[1]+t1[2],t2[1]);
for(int i=3;i<=k;i++){
dp[i]=min(dp[i-1]+t1[i],dp[i-2]+t2[i-1]);
}
int ans=dp[k];
Time(ans);
}
return 0;
}HDU1257 最少拦截系统
题目是说，对于一连串导弹，一套拦截系统所能拦截的导弹的高度不能大于该系统上一次拦截的导弹的高度。问要拦截所有的导弹，最少要多少套拦截系统。
这题直接贪心模拟即可，对于每一发导弹，检查当前存在的拦截系统是否可以将其拦截。如果存在一套拦截系统可以将该导弹拦截，就将此系统的高度改为该导弹的高度；如果不存在，就添加一套系统，并将其高度设为当前导弹的高度。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int arr[maxn];
int sys[maxn];
int main()
{
IOS;
int n;
while(cin>>n){
for(int i=0;i<n;i++)
cin>>arr[i];
int cnt=0;sys[cnt++]=arr[0];
for(int i=1;i<n;i++){
bool flag=0;
for(int j=0;j<cnt;j++){
if(sys[j]>=arr[i]){
flag=1;sys[j]=arr[i];
break;
}
}
if(!flag)
sys[cnt++]=arr[i];
}
cout<<cnt<<endl;
}
return 0;
}当然，因为sys数组是单调不减的，所以也可以将内层循环优化为二分。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int arr[maxn];
int sys[maxn];
int main()
{
IOS;
int n;
while(cin>>n){
for(int i=0;i<n;i++)
cin>>arr[i];
int cnt=0;sys[cnt++]=arr[0];
for(int i=1;i<n;i++){
int* pos=lower_bound(sys,sys+cnt,arr[i]);
int idx=pos-sys;
if(pos==sys+cnt)
sys[cnt++]=arr[i];
else
sys[idx]=arr[i];
}
cout<<cnt<<endl;
}
return 0;
}