队友的建议，让我去学一学kuangbin的基础dp，在这里小小的整理总结一下吧。
首先我感觉自己还远远不够称为一个dp选手，一是这些题目还远不够，二是定义状态的经验不足。不过这些题目让我在一定程度上加深了对dp的理解，但要想搞好dp，还需要多多练习啊。
HDU - 1024 开场高能
给出一个数列，分成m段，求这m段的和的最大值，dp[i][j]表示遍历到第i个数，已经划分了j段，对于每一个数有两种决策，加入上一个区间段，自己成为一个区间段，故dp[i][j] = max(dp[i-1][j]+a[i],dp[k][j-1]+a[i]) 1<=k<=i-1,二维数组肯定不能开，所以使用两个数组，另一个数组保存上一次的状态，这样也可以及时的获得第二种情况的答案，然后再更新一遍旧状态就可以。一开始因为初始化问题错了几次。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 1e6+;
const int INF = 1e9;
#define LL long long
LL dp1[N],dp2[N];
LL a[N];
int main() {
int n,m;
while(~scanf("%d%d",&m,&n)) {
for(int i=; i <=n; i++) {
scanf("%lld",&a[i]);
dp1[i] = dp2[i] = ;
}
dp1[] = ;
dp2[] = ;
for(int i =; i <= m; i++) {
LL Max = -INF;
for(int j=i; j <= n; j++) {
Max = max(Max,dp2[j-]);
dp1[j] = max(dp1[j-]+a[j],Max+a[j]);
}
for(int j =i; j <= n; j++) {
dp2[j] = dp1[j];
}
}
LL ans = -INF;
for(int i = m; i <= n; i++) {
ans = max(ans,dp1[i]);
}
printf("%lld\n",ans);
}
return ;
}
HDU - 1029 感觉跟dp没啥关系
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e6+;
#define LL long long
LL a[N];
int main(){
int n;
while(~scanf("%d",&n)){
for(int i = ;i < n;i++){
scanf("%lld",&a[i]);
}
sort(a,a+n);
printf("%lld\n",a[n/]);
}
return ;
}
HDU - 1069 线性dp，排序后求最大权值
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Rec{
int c,k,g;
}r[];
void setRec(int id,int x,int y,int z){
r[id].c = x;
r[id].k = y;
r[id].g = z;
}
int dp[];
bool ok(int i,int j){
if(r[i].c<r[j].c && r[i].k<r[j].k) return true;
if(r[i].c<r[j].k && r[i].k<r[j].c) return true;
return false;
}
bool cmp(Rec a,Rec b){
return (a.c*a.k > b.c*b.k);
}
int main()
{
int n,x,y,z,ca=;
while(~scanf("%d",&n)){
if(!n) break;
for(int i = ;i <= *n;i += ){
scanf("%d%d%d",&x,&y,&z);
setRec(i,x,y,z);
setRec(i+,x,z,y);
setRec(i+,y,z,x);
}
n = n*;
sort(r+,r+n+,cmp);
for(int i=;i <= n;i++){
// cout<<r[i].c<<" "<<r[i].k<<" "<<r[i].g<<endl;
dp[i] = r[i].g;
for(int j = ;j < i;j++){
if(ok(i,j)){
dp[i] = max(dp[i],dp[j]+r[i].g);
}
}
}
int ans = ;
for(int i = ;i <= n;i++){
ans = max(ans,dp[i]);
}
printf("Case %d: maximum height = %d\n",++ca,ans);
}
}
HDU - 1074 之前就做过，但基础dp里居然有状态压缩，因为这里只是求做作业的顺序，从小到大枚举所有状态，对于每一个状态，添加一个作业递推出新的状态，如果一个状态可以由多个途径达到，选择一个最优的，当所有作业选完以后就是答案，回溯状态输出一下就可以。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 15
#define M (1<<N)+N
const int INF = 1e9;
struct DP {
int day,red,fa;
} dp[M];
struct Course {
string name;
int dl,cost;
} c[N];
void outPut(int k,int n) {
int f = dp[k].fa;
if(f == -) return;
outPut(f,n);
for(int i =; i < n; i++) {
if((k&(<<i))!= && (f&(<<i))==) {
cout<<c[i].name<<endl;
break;
}
}
}
int main() {
int T,n,day;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i = ; i < n; i++) {
cin>>c[i].name>>c[i].dl>>c[i].cost;
}
int up = (<<n);
for(int i = ; i < up; i++) {
dp[i].fa = -;
}
dp[].day = dp[].red = ;
for(int i=; i < up; i++) {
for(int j=; j<n; j++) {
if((i&(<<j)) == ) {
int k = (i|(<<j));
int nday = dp[i].day+c[j].cost;
dp[k].day = nday;
int nred = max(,nday-c[j].dl);
if(dp[k].fa == -) {
dp[k].red = dp[i].red+nred;
dp[k].fa = i;
} else if(dp[k].red > dp[i].red+nred) {
dp[k].red = dp[i].red+nred;
dp[k].fa = i;
}
}
}
}
printf("%d\n",dp[up-].red);
outPut(up-,n);
}
return ;
}
HDU - 1087 最长递增子序列
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
#define N 1005
const int INF = 1e9;
LL dp[N],a[N];
int main()
{
int n;
while(~scanf("%d",&n)){
if(!n) break;
LL ans = -INF;
for(int i = ;i < n;i++){
scanf("%lld",&a[i]);
dp[i] = a[i];
for(int j = ;j < i;j++){
if(a[i]>a[j]) dp[i] = max(dp[i],dp[j]+a[i]);
}
ans = max(ans,dp[i]);
}
printf("%lld\n",ans);
}
return ;
}
HDU - 1114 完全背包，恰好装满，一开始初始化-1为不可达状态，状态转移的时候判断一下不可达状态就可以
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = ;
const int M = ;
int dp[N];
struct Thing{
int p,w;
}t[M];
int main()
{
int T,E,F,n;
scanf("%d",&T);
while(T--){
scanf("%d%d",&E,&F);
int all = F-E;
scanf("%d",&n);
for(int i = ;i <n;i++){
scanf("%d %d",&t[i].p,&t[i].w);
}
memset(dp,-,sizeof(dp));
dp[] = ;
for(int i = ;i < n;i++){
for(int j =t[i].w; j<= all;j++){
int Last = j-t[i].w;
if(dp[Last] == -) continue;
if(dp[j]==-) dp[j] = dp[Last]+t[i].p;
else dp[j] = min(dp[j],dp[Last]+t[i].p);
}
}
if(dp[all] == -){
printf("This is impossible.\n");
}else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[all]);
}
return ;
}
HDU - 1176 数塔，倒着算
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100005
int dp[][N],a[][N];
int main()
{
int n,t,x,Mt;
while(~scanf("%d",&n)){
if(!n) break;
memset(a,,sizeof(a));
Mt = ;
for(int i=;i<n;i++){
scanf("%d%d",&x,&t);
a[x][t]++;
Mt = max(Mt,t);
}
for(int i=;i<=;i++){
dp[i][Mt+] = ;
}
for(int i=Mt;i>=;i--){
for(int j=;j <= ;j++){
int Max = -;
if(j==) Max = max(dp[j][i+],dp[j+][i+]);
else if(j==) Max = max(dp[j][i+],dp[j-][i+]);
else Max = max(max(dp[j][i+],dp[j+][i+]),dp[j-][i+]);
dp[j][i] = Max + a[j][i];
}
}
printf("%d\n",dp[][]);
}
return ;
}
HDU - 1260 基础dp，12点的时候算am，还是pm呢。。题目中都没有这组样例，我还困惑了一会
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 2005
int a[N],b[N],dp[N];
int main() {
int T,n;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=; i<=n; i++) {
scanf("%d",&a[i]);
}
for(int i=; i<=n; i++) {
scanf("%d",&b[i]);
}
dp[] = ;
for(int i=; i<=n; i++) {
if(i==) dp[i] = a[i];
else dp[i] = min(dp[i-]+a[i],dp[i-]+b[i]);
}
int tmp = dp[n];
int s = tmp%;
tmp /= ;
int m = tmp%;
tmp /= ;
int h = tmp%+;
h %= ;
bool f = true;
if(h == ) f = false;
if(h > ) {
h -= ;
}
printf("%02d:%02d:%02d ",h,m,s);
if(f) printf("am\n");
else printf("pm\n");
}
return ;
}
HDU - 1257 这个题目是有争议的，但是我认为这个题目就是让求，将此序列划分为最长递减序列的最少条数，dp[i]代表第i个子序列的最小值，一个数的决策，当然是加入到距离dp[i]最小的那一个，这样能保证条数最少，而这样做正好就对应了kuangbin的贪心代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e6;
const int INF = 1e9;
int dp[N]; ///dp[i]表示第i个子序列的最小值
int main()
{
int n,m,tmp;
while(~scanf("%d",&n)){
m = ;
for(int i=;i<n;i++){
scanf("%d",&tmp);
int Min = INF,End=-;
for(int j =;j < m;j++){
if(tmp<=dp[j] && dp[j]-tmp < Min){
Min = min(Min,dp[j]-tmp);
End = j;
}
}
if(End == -) dp[m++] = tmp;
else dp[End] = tmp;
}
printf("%d\n",m);
}
return ;
}
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = ;
const int INF = 1e9;
struct DP{
int len,pre;
}dp[N];
struct Mice{
int w,s,id;
}m[N];
bool cmp(Mice a,Mice b){
if(a.w != b.w) return a.w < b.w;
else return a.s < b.s;
}
int Stack[N];
int main()
{
// freopen("in.cpp","r",stdin);
int tot=;
while(scanf("%d %d",&m[tot].w,&m[tot].s) != EOF){
m[tot].id = tot;
tot++;
}
sort(m,m+tot,cmp);
for(int i =;i < tot;i++){
dp[i].len = ;
dp[i].pre = -;
for(int j=;j<i;j++){
if(m[i].w>m[j].w && m[i].s<m[j].s){
if(dp[i].len < dp[j].len+){
dp[i].len = dp[j].len+;
dp[i].pre = j;
}
}
}
}
int Max = -INF,End=-;
for(int i=;i<tot;i++){
if(dp[i].len > Max){
Max = dp[i].len;
End = i;
}
}
printf("%d\n",Max);
int top=;
while(End != -){
Stack[top++] = m[End].id+;
End = dp[End].pre;
}
while(top != ){
printf("%d\n",Stack[--top]);
}
return ;
}
POJ - 1015 这里面我感觉这个题是很难的了，因为我没有找到状态的正确定义，原来是dp[i][k]代表已经选出i个人，差为k的最大和，使用path记录每个状态的决策，在选人的时候通过回溯判断这个人是否已经被选过，我一开始用的vis，各种wa，还没有明白是怎么回事，一开始平移区间还移出了毛病。。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = ;
const int INF = 1e9;
int dp[][],path[][];
int cha[N],he[N],x[N],y[N],n,m;
///使用path记录此状态选的是哪一个人
bool ok(int i,int j,int k) {
while(i> && path[i][j] != -) {
if(path[i][j] == k) return false;
j -= cha[path[i][j]];
i--;
}
return true;
}
int out[N],os,p,d;
void Print(int i,int j) {
os = p = d = ;
while(i> && path[i][j] != -) {
int k = path[i][j];
j -= cha[k];
i--;
out[os++] = k;
p += x[k];
d += y[k];
}
}
int main() {
int ca=;
while(~scanf("%d%d",&n,&m)) {
if(n== && m==) break;
for(int i = ; i <= n; i++) {
scanf("%d%d",&x[i],&y[i]);
cha[i] = x[i]-y[i];
he[i] = y[i]+x[i];
}
memset(dp,-,sizeof(dp));
memset(path,-,sizeof(path));
int km = m*;
dp[][km] = ;
for(int i=; i<m; i++) {
for(int j=; j<=*km; j++) {
if(dp[i][j] == -) continue;
for(int k=; k<=n; k++) {
int nj = j+cha[k];
if(!ok(i,j,k)) continue;
if(dp[i+][nj]<dp[i][j]+he[k]) {
dp[i+][nj] = dp[i][j] + he[k];
path[i+][nj] = k;
}
}
}
}
int Min = INF,End=-,Max = -INF;
for(int i = ; i <= *km; i++) {
if(dp[m][i]!=-) {
if(abs(i-km)<Min) {
Min = abs(i-km);
End = i;
Max = dp[m][i];
} else if(abs(i-km) == Min&&dp[m][i]>Max) {
End = i;
Max = dp[m][i];
}
}
}
printf("Jury #%d\n",++ca);
Print(m,End);
printf("Best jury has value %d for prosecution and value %d for defence:\n",p,d);
sort(out,out+os);
for(int i = ; i < os; i++) {
printf(" %d",out[i]);
}
printf("\n\n");
}
return ;
}
POJ - 1458 最长公共子串
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e3 + ;
const int INF = 1e9;
char a[N],b[N];
int dp[N][N];
int main()
{
while(~scanf("%s%s",a+,b+)){
int lena = strlen(a+);
int lenb = strlen(b+);
memset(dp,,sizeof(dp));
for(int i = ;i <= lena;i++){
for(int j=;j <= lenb;j++){
if(i==||j==) dp[i][j] = ;
else{
if(a[i]==b[j]) dp[i][j] = dp[i-][j-]+;
dp[i][j]=max(dp[i][j],max(dp[i-][j],dp[i][j-]));
}
}
}
printf("%d\n",dp[lena][lenb]);
}
return ;
}
POJ - 1661 它只能从板的两边下落这是最重要的，dp[i][2]代表从第i个板子的左边或者右边掉到地上所需的最少时间，然后这就变成了线性dp，正常转移即可，然后有几个小坑，比如有可能直接落到地上，一开始忘记考虑这个wa了一发
POJ - 2533 最长递增子序列
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e3 + ;
const int INF = 1e9;
int dp[N],a[N];
int main()
{
int n,ans;
while(~scanf("%d",&n)){
ans = -INF;
for(int i = ;i < n;i++){
scanf("%d",&a[i]);
dp[i] = ;
for(int j=;j<i;j++){
if(a[i]>a[j]){
dp[i] = max(dp[i],dp[j]+);
}
}
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
}
}
POJ - 3186 因为只能从最上面和最下面选数，所以可以定义状态，dp[i][j]表示从i到j还没有被选出所能到达的最大值
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e3 + ;
const int INF = 1e9;
int dp[N][N],a[N];
int main()
{
int n;
while(~scanf("%d",&n)){
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
for(int j=n;j>=i;j--){
int nd = n-(j-i+);
if(i== && j==n) continue;
if(j!=n) dp[i][j]=max(dp[i][j],dp[i][j+]+a[j+]*nd);
if(i!=) dp[i][j]=max(dp[i][j],dp[i-][j]+a[i-]*nd);
}
}
int ans = -INF;
for(int i=;i<=n;i++){
ans = max(ans,dp[i][i]+a[i]*n);
}
printf("%d\n",ans);
}
return ;
}
HDU - 1078 记忆化搜索，一开始读错了题，以为k步可以拐弯，想复杂了
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = ;
const int INF = 1e9;
int dp[N][N],n,k;
int mp[N][N],go[][]= {,,-,,,-,,};
bool inMap(int x,int y) {
return (x>=&&x<n&&y>=&&y<n);
}
int dfs(int x,int y) {
if(dp[x][y] != -) return dp[x][y];
int Max = ,nx,ny;
for(int j =; j<=k; j++) {
for(int i = ; i < ; i++) {
nx = x + go[i][]*j;
ny = y + go[i][]*j;
if(inMap(nx,ny) && mp[nx][ny] > mp[x][y]) {
Max = max(Max,dfs(nx,ny));
}
}
}
return dp[x][y] = mp[x][y] + Max;
}
int main() {
while(~scanf("%d%d",&n,&k)) {
if(n==- && k==-) break;
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
scanf("%d",&mp[i][j]);
}
}
memset(dp,-,sizeof(dp));
int ans = dfs(,);
printf("%d\n",ans);
}
return ;
}
HDU - 2859 挺巧妙的题，沿着对角线扩展，dp[i][j]表示以(i,j)位置为右上角所能形成的最大对称矩阵，转移状态的时候需要注意，dp[i-1][j+1]如果大于上一个状态，直接由上一个状态加1，如果小于等于上一个状态，那么就等于延伸的最大长度，他的正确性由前一个状态保证
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = ;
const int INF = 1e9;
char mp[N][N];
int dp[N][N];
int main()
{
int n,ans;
while(~scanf("%d",&n)){
if(n==) break;
for(int i=;i<=n;i++){
scanf("%s",mp[i]+);
}
for(int i=;i<=n;i++){
dp[i][] = dp[n][i] = ;
}
ans = ;
for(int i=n-;i>=;i--){
for(int j=;j<=n;j++){
int len = ;
while(j-len>=&&i+len<=n && mp[i+len][j]==mp[i][j-len]){
len++;
}
// cout<<mp[i][j]<<" len = "<<len<<endl;
if(len >= dp[i+][j-]+) {
dp[i][j] = dp[i+][j-]+;
}else dp[i][j] = len;
ans = max(ans,dp[i][j]);
}
}
printf("%d\n",ans);
}
return ;
}
POJ - 3616 被这个题晃了一下，本来就是个线性dp，跟n没关系
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e3+;
const int INF = 1e9;
int dp[N];
struct Thing{
int l,r,w;
}t[N];
bool cmp(Thing a,Thing b){
if(a.l != b.l) return a.l < b.l;
return a.r < b.r;
}
int main()
{
int n,m,r,ans;
while(~scanf("%d%d%d",&n,&m,&r)){
for(int i=;i<=m;i++){
scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].w);
}
ans = -INF;
sort(t+,t++m,cmp);
for(int i=;i<=m;i++){
dp[i] = t[i].w;
for(int j=;j < i;j++){
if(t[i].l >= t[j].r+r){
dp[i] = max(dp[i],dp[j]+t[i].w);
}
}
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
}
return ;
}
POJ - 3666 将一个序列修改为有序序列的最小花费，对于一个长度为n的序列，如果将他改成非递减的序列，那么可以证明最后一个数可以是这个序列的最大值，而不影响答案，对n+1的序列也是如此，归纳知最终序列中的数可以全部来自原先序列，定义dp[i][j]为选到第i个数，最后一个数为有序序列的第j个数的最小值，滚动数组，枚举上一个状态的结尾数，之所以要排序是因为要保证这个序列的有序性，正序倒序分别求一次就可以得到最优解。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = ;
const int INF = 1e9;
int a[N],dp[N],n,b[N];
int fun1(){
sort(b+,b++n);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
int Min = INF;
for(int j=;j<=n;j++){
Min = min(Min,dp[j]);
dp[j] = Min+abs(a[i]-b[j]);
}
}
int res = INF;
for(int i=;i<=n;i++){
res = min(res,dp[i]);
}
return res;
}
bool cmp(int a,int b){
return a > b;
}
int fun2(){
sort(b+,b++n,cmp);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
int Min = INF;
for(int j=;j<=n;j++){
Min = min(Min,dp[j]);
dp[j] = Min+abs(a[i]-b[j]);
}
}
int res = INF;
for(int i=;i<=n;i++){
res = min(res,dp[i]);
}
return res;
}
int main() {
int ans;
while(~scanf("%d",&n)) {
for(int i=; i<=n; i++) {
scanf("%d",&a[i]);
b[i] = a[i];
}
ans = min(fun1(),fun2());
printf("%d\n",ans);
}
return ;
}