#### 题意是说，有两个整数序列\(W\)和\(S\)，要求找出一组下标\(m_1,m_2,m_3,···,m_n\)，使得\[W[m_1]<W[m_2]<W[m_3]<···<W[m_n]\]且\[S[m_1]>S[m_2]>S[m_3]>···>S[m_n]\]。下标的个数应尽可能地多。要求输出下标的个数以及被选出的下标。
对所有的\(W-S\)对进行排序，排序规则是按\(W\)为第一关键字从小到大排序，按\(S\)为第二关键字从大到小排序。而dp的方法其实跟LIS或者最大上升子序列和是很像的。关于输出被选取的下标，其实就是记录路径，只需要用一个pre数组记录下每一个下标的前驱，然后递归回去即可。
#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;
struct node{
int wei;
int speed;
int id;
bool operator<(const node& nn)const{
if(wei!=nn.wei)
return wei<nn.wei;
else
return speed>nn.speed;
}
};
node ns[1005];
int pre[1005];
int dp[1005];
void show(int todo)
{
if(pre[todo]==-1){
cout<<ns[todo].id<<endl;
return ;
}
show(pre[todo]);
cout<<ns[todo].id<<endl;
}
int main()
{
IOS;
int w,s;int cnt=0;
int ID=0;
mst(pre,-1);
while(cin>>w>>s){
ns[cnt].wei=w;
ns[cnt].id=++ID;
ns[cnt++].speed=s;
}
sort(ns,ns+cnt);
int idx=0;
int last=0;
int ans=0;
for(int i=0;i<cnt;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(ns[j].wei<ns[i].wei&&ns[j].speed>ns[i].speed){
if(dp[i]<dp[j]+1){
dp[i]=dp[j]+1;
pre[i]=j;
}
}
}
int tmp=ans;
ans=max(ans,dp[i]);
if(ans!=tmp)
last=i;
}
cout<<ans<<endl;
show(last);
return 0;
}POJ1015 Jury Compromise
已有题解，不再赘述（确实是道好题）
POJ1458 Common Subsequence
题如其名，最长公共子序列。直接写就可。
#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 dp[1005][1005];
int main()
{
string sa,sb;
while(cin>>sa>>sb){
mst(dp,0);
int lena=sa.size();
int lenb=sb.size();
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;j++){
if(sa[i-1]==sb[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[lena][lenb]<<endl;
}
return 0;
}POJ1661 Help Jimmy
题目大意不知道怎么描述......
思路就是从最下面的平台往上dp，\(dp[i][0]\)表示的是从当前平台往左走一直到下一个平台的边缘（左边缘或右边缘）所需要的最小时间。\(dp[i][1]\)表示的是从当前平台往右走一直到下一个平台的边缘（左边缘或右边缘）所需要的最小时间。此处的最小时间指的是从最下面的平台一直递推到当前平台的总时间。
代码如下：
#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;
struct node{
int lef,rig;
int hei;
bool operator<(const node& nn)const{
return hei>nn.hei; //从大到小
}
};
node ns[1005];
int dp[1005][2];
int n,x,y,maxi;
void left_(int i)
{
int k;
for(k=i+1;k<=n+1;k++){ //k在i下面
if(ns[k].lef<=ns[i].lef
&&ns[k].rig>=ns[i].lef
&&ns[i].hei-ns[k].hei<=maxi){
if(k==n+1)
dp[i][0]=ns[i].hei-ns[k].hei;
else
dp[i][0]=ns[i].hei-ns[k].hei+min(dp[k][0]+ns[i].lef-ns[k].lef,dp[k][1]+ns[k].rig-ns[i].lef);
return ;
}
}
if(ns[i].hei-ns[k].hei>maxi)
dp[i][0]=INF;
return ;
}
void right_(int i)
{
int k;
for(k=i+1;k<=n+1;k++){ //k在i下面
if(ns[k].lef<=ns[i].rig
&&ns[k].rig>=ns[i].rig
&&ns[i].hei-ns[k].hei<=maxi){
if(k==n+1)
dp[i][1]=ns[i].hei-ns[k].hei;
else
dp[i][1]=ns[i].hei-ns[k].hei+min(dp[k][0]+ns[i].rig-ns[k].lef,dp[k][1]+ns[k].rig-ns[i].rig);
return ;
}
}
if(ns[i].hei-ns[k].hei>maxi)
dp[i][1]=INF;
return ;
}
int main()
{
IOS;
int t;cin>>t;
while(t--){
mst(dp,0);
cin>>n>>x>>y>>maxi;
for(int i=1;i<=n;i++){
cin>>ns[i].lef>>ns[i].rig>>ns[i].hei;
}
sort(ns+1,ns+1+n);
dp[n+1][0]=dp[n+1][1]=0;
ns[n+1].lef=-INF;ns[n+1].rig=INF;ns[n+1].hei=0;
ns[0].lef=ns[0].rig=x;ns[0].hei=y;
for(int i=n;i>=0;i--){
left_(i);
right_(i);
}
int ans=min(dp[0][1],dp[0][0]);
cout<<ans<<endl;
}
return 0;
}POJ2533 Longest Ordered Subsequence
题如其名，直接转移即可。注意初始化。
#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 dp[1005];
int arr[1005];
int main()
{
IOS;
int n;cin>>n;
mst(dp,0);
for(int i=1;i<=n;i++)
cin>>arr[i];
for(int i=1;i<=n;i++) dp[i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(arr[j]<arr[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int ans=-1;
for(int i=1;i<=n;i++)
ans=max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}POJ3186 Treats for the Cows
题意懒得描述了......
\(dp[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=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int arr[2005];
int dp[2005][2005];
int main()
{
IOS;
int n;cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i],dp[i][i]=arr[i];
mst(dp,0);
int age=1;
int cnt=0;
for(int i=n-1;i>=1;i--)
for(int j=i;j<=n;j++)
dp[i][j]=max(dp[i+1][j]+arr[i]*(n-j+i),dp[i][j-1]+arr[j]*(n-j+i));
int ans=dp[1][n];
cout<<ans<<endl;
return 0;
}HDU1078 FatMouse and the Cheese
题目大意是说，现在有\(n \times n\)个网格，这些网格中有若干个网格放有cheese。从网格\((0,0)\)出发，每次走到下一个放有cheese的地方，可以水平走、垂直走，可以回头，每次最多走\(k\)步；同时，每一次获得的cheese都应该比上一次多，问最终最多能得到多少cheese。
一开始想着状态要怎么转移，感觉这题的规则挺多，不太好转移......然而实际上只需要记忆化+爆搜+简单dp即可。
代码如下：
#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 mp[1005][1005];
int dp[1005][1005];
int dir[4][2]=<!--swig0-->;
int n,k;
int dfs(int x,int y)
{
if(dp[x][y]) return dp[x][y];
int sum=0;
int tx=0;int ty=0;
for(int i=0;i<4;i++){
for(int j=1;j<=k;j++){
tx=x+j*dir[i][0];
ty=y+j*dir[i][1];
if(tx<n&&0<=tx&&ty<n&&0<=ty){
if(mp[tx][ty]>mp[x][y])
sum=max(sum,dfs(tx,ty));
}
}
}
dp[x][y]=sum+mp[x][y];
return dp[x][y];
}
int main()
{
IOS;
while(cin>>n>>k&&n!=-1&&k!=-1){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>mp[i][j];
mst(dp,0);
cout<<dfs(0,0)<<endl;
}
return 0;
}HDU2859 Phalanx
题目大意是说，从一个矩阵中找出一个关于自身右对角线（从右上到左下）对称的子矩阵，问能找到的符合要求的最大子矩阵的大小是多少。
\(dp[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=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char mp[1005][1005];
int dp[1005][1005];
int main()
{
IOS;
int n;
while(cin>>n&&n){
for(int i=0;i<n;i++){
string str;cin>>str;
for(int j=0;j<n;j++){
mp[i][j]=str[j];
}
}
if(n==1){
cout<<"1"<<endl;
continue;
}
mst(dp,0);int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x=i-1;int y=j+1;
while(x>=0&&y<n){
if(mp[x][j]!=mp[i][y])
break;
x--;y++;
}
int sz=y-j;
if(sz>dp[i-1][j+1])
dp[i][j]=dp[i-1][j+1]+1;
else
dp[i][j]=sz;
ans=max(ans,dp[i][j]);
}
}
cout<<ans<<endl;
}
return 0;
}POJ3616 Miking Time
将每一个时间段的结束时间加上休息时间，即可用最大上升子序列和的思路来做。
代码如下：
#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;
struct node{
int s,e,eff;
bool operator<(const node& nn)const{
if(s!=nn.s) return s<nn.s;
return e<nn.e;
}
};
node ns[1005];
int dp[1005];
int main()
{
IOS;
int n,m,r;
cin>>n>>m>>r;
for(int i=1;i<=m;i++){
cin>>ns[i].s>>ns[i].e>>ns[i].eff;
ns[i].e+=r;
}
sort(ns+1,ns+1+m);
mst(dp,0);
for(int i=1;i<=m;i++){
dp[i]=ns[i].eff;
for(int j=1;j<i;j++){
if(ns[j].e<=ns[i].s){
dp[i]=max(dp[j]+ns[i].eff,dp[i]);
}
}
}
int ans=-1;
for(int i=1;i<=m;i++)
ans=max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}POJ3666 Making the Grade
题目大意是说，对于一个给定的序列，现在要把它变成递增的或递减的，每改动一个数要付出的代价为改动后的数与改动前的数的差的绝对值。问如何改动才能使得代价最小。
首先，这题的数据有点问题，只需要考虑递增的情况......
这题的状态转移也不太好想，甚至感觉有点......神奇。具体见代码及代码注释
#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=1e3+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int abs_(int todo)
{
if(todo<0) return -todo;
return todo;
}
int arr[maxn<<1];
int b[maxn<<1];
int dp[maxn<<1][maxn<<1]; //dp[i][j]表示前i个数,最后一个数在arr[]中第j小
int main()
{
IOS;
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
b[i]=arr[i];
}
sort(b+1,b+n+1); //? 为什么要排序?为什么不排序就会不行?
//如果排序是为了去重，那去重的意义是什么?以及，为什么我不去重也能过?
mst(dp,0);
for(int i=1;i<=n;i++){
int tmp=INF;
for(int j=1;j<=n;j++){
tmp=min(dp[i-1][j],tmp);
//k:[1,j],这一层循环可以省掉,维护一个最小值即可
//可以保证tmp一定是范围[1,j]内最小的
dp[i][j]=abs_(arr[i]-b[j])+tmp;
}
}
int ans=INF;
for(int i=1;i<=n;i++)
ans=min(ans,dp[n][i]);
cout<<ans<<endl;
return 0;
}