前言：

特长生必有一道DP，所以就做了一些很经典的例题

T1：最小代价问题

思路：

这题其实可以直接dfs搜代价最小的路径，但可能回T，所以用DP
设f[i][j]表示从（1,1）走到（i,j）的时候取得最大值
则状态转移方程为：

f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) f[i][j] = max(f[i - 1][j], f[i][j - 1]) f[i][j]=max(f[i−1][j],f[i][j−1])

C o d e Code Code:

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;
int n, m, a[1001][1001], f[1001][1001], i, j;
bool go[1001][1001];
void print (int x,int y)//输出路径
{
	if(x == 1 && y == 1) {printf("(1,1)");return;}
	if(go[x][y]) print(x - 1, y);
	else print(x, y - 1);
	printf("->(%d,%d)", x, y);
}
void dp ()//dp
{
	memset (f,127 / 3,sizeof(f));//初始化
	f[1][1] = a[1][1];//等于图中的（1,1）
	for (int i = 1; i <= n ; ++i)
	  for (int j = 1; j <= m ; ++j)
	  {
	  	if (i == 1 && j == 1) continue;
	  	if (f[i - 1][j] < f[i][j - 1])//转移
	  	{
	  		go[i][j] = true;
	  		f[i][j] = f[i - 1][j] + a[i][j];
	  	}else
		    f[i][j] = f[i][j - 1] + a[i][j];
	  }
}
int main ()
{
	scanf("%d%d",&n, &m);
	for (int i = 1; i <= n; ++i)
	  for (int j = 1; j <= m; ++j)
	  {
	    scanf("%d", &a[i][j]);
		if (a[i][j] == 0) a[i][j] = 212313121;//初始化
	  }
	dp ();
    print (n,m);//输出路径
	printf("\n%d", f[n][m] - a[n][m]);  
	  
}

T2：数字金字塔

思路：

这题顺推逆推都可以比较简单吧

C o d e Code Code:

#include<cstdio>
#include<iostream> 
using namespace std; 
int a[10000],f[10000];
int n,ans = 0;
int main()
{
  scanf("%d",&n);
  scanf("%d",&a[1]);
  f[1] = a[1]; 
  for (int i = 2;i <= n; i++)
  {
      for(int j = 1; j <= i; j++)
      scanf("%d", &a[j]);
      for(int j = i; j >= 2; j--)
      {
        f[j] = max(f[j - 1], f[j]) + a[j]; //dp
        ans = max(ans, f[j]);
      }
      f[1] = a[1] + f[1]; 
      ans = max(ans, f[1]);
  }

  printf("%d",ans);
  return 0;
}

T3：求最长不下降序列

思路：

设f[i]为前i个数中的最大不下降序列长度 , 则

f [ i ] = m a x ( f [ i ] , f [ j ] + 1 ) f[i]=max(f[i],f[j]+1) f[i]=max(f[i],f[j]+1)

C o d e Code Code:

#include<cstdio>
#include<iostream>
using namespace std;
int m, n, a[1001], sum[1001];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	  {
	  	scanf("%d", &a[i]);
	  	sum[i] = 1;
	  	for (int j = 1; j < i; j++)
	  	  if (a[j] < a[i] && sum[j] >= sum[i])
	  	    sum[i] = sum[j] + 1;//dp
	  	m = max(m, sum[i]);
	  }
	printf("%d",m);
}

T4:采药（01背包）

思路：

01背包模板，选或不选使价值最大化

C o d e Code Code:

#include<cstdio>
#include<iostream>
using namespace std;
int m,v[1001],dp[1001],a[1001],w;
int main()
{
  scanf("%d%d",&m,&w);
  for(int i = 1; i <= w; i++)scanf("%d%d",&v[i],&a[i]);
  for(int i = 1; i <= w; i++)
    for(int g = m; g >= v[i]; g--) 
  dp[g] = max(dp[g], dp[g - v[i]] + a[i]); //一维01背包
  printf("%d",dp[m]);
  return 0;
}

T5：完全背包

思路：

其实和01背包差不多，只不过01背包是选了就不能再选，完全背包则是选了可以重复选

C o d e Code Code:

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,x,y,ans[10001];
int main()
{
	
  scanf("%d%d",&n,&m);
  for(int i = 1;i <= m;++i)
  {
   scanf("%d%d",&x,&y);
   for(int j = x;j <= n; j++)
   ans[j] = max(ans[j], ans[j - x] + y);
 }
  printf("%d",ans[n]);
  return 0;
}

T6:最大连续数列的和

思路：

设f[i]为以元素ai结尾的子序列的最大值，f[i]的取值只有两种可能，一是ai单独成为一个序列，二是将ai加入到前面的ai-1序列中，可以知道f[i]的取值只与a1,a2,…,ai-1有关，与ai+1…an无关,所以本题满足最优化原则。
则状态转移方程为：

f [ i ] = m a x ( a [ i ] , f [ i − 1 ] + a [ i ] ) f[i] = max (a[i], f[i - 1] + a[i]) f[i]=max(a[i],f[i−1]+a[i])

C o d e Code Code:

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n;
int a[1001],f[1001];
int main ()
{
	int ans = 0;
	memset(f,0,sizeof(0));
	scanf("%d",&n);
	for (int i = 1; i <= n; ++i)
	    scanf("%d", &a[i]);
	f[1] = a[1];//初始化
	for (int i = 2; i <= n; ++i)
	{
	  f[i] = f[i - 1] + a[i];//DP
	  if (f[i] < 0) f[i] = 0;
	  ans = max (ans,f[i]);	
	}
	
	printf("%d",ans);
}

T7:合并石子

思路：

我们可以想到，此处是由2堆石子合并，所以最终最优解肯定是由两个局部最优解的加上整体的和求得。
可以推出状态转移方程

f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] + s [ j ] − s [ i − 1 ] ) f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]−s[i−1])

C o d e Code Code:

#include<cstdio>
#include<iostream>
using namespace std;
int n,f[1000][1000],s[1000],maxn;
int main()
{
	memset(f,127 / 3,sizeof(f));
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
    {
      scanf("%d",&maxn);
	  s[i] = s[i - 1] + maxn;//前缀和
	  f[i][i] = 0;  
    }
    for(int i=n-1;i>=1;i--)
	  for(int j=i+1;j<=n;j++)
	    for(int k=i;k<=j-1;k++) 
	      f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]); //dp


	  printf("%d",f[1][n]);
	  return 0; 
}

T8:机器分配

思路

。用机器数来做状态，数组f[]i[]j表示前I个公司分配J台机器的最大盈利。则状态转移方程为

f [ i ] [ j ] = m a x ( f [ i − 1 ] [ k ] + a [ i ] [ j − k ] , f [ i ] [ j ] ) f[i][j] =max (f[i-1][k] + a[i][j-k],f[i][j]) f[i][j]=max(f[i−1][k]+a[i][j−k],f[i][j])

然后我们可以把他压成一维

f [ j ] = m a x ( f [ j ] , f [ j − k ] + a [ i ] [ k ] ) ; f[j] = max(f[j], f[j - k] + a[i][k]); f[j]=max(f[j],f[j−k]+a[i][k]);

C o d e Code Code:

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,a[100][100],f[100];
int main()
{
	scanf("%d%d",&m,&n);
	for(int i = 1;i <= m;i++)
		for(int j = 1;j <= n;j++)
		scanf("%d",&a[j][i]);
	for(int i = 1; i <= n; i++)
	for(int j = m; j >= 0; j--)
	for(int k = 1; k <= j; k++)
	    f[j] = max(f[j], f[j - k] + a[i][k]);//dp
	printf("%d",f[m]);
	return 0;

}

T9:叠放箱子问题

思路：

考虑第i个箱子放与不放的问题

C o d e Code Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[1005],b[1005],f[1005][1005],u;
int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
	  scanf("%d%d", &a[i], &b[i]); 
	  for(int i = 1;i <= n; i++)
	    for(int j = 1; j <= n; j++)
	      f[i][j] = 2147483647 / 3;
	    u = 2147483647 / 3;
	  f[n][1] = a[n];
	  for(int i = n - 1; i >= 1; i--)
	  {memcpy(f[i],f[i+1],sizeof(f[i]));
	  	for(int j = 0; j <= n - i; j++)
	  	{
	  		if(f[i + 1][j] <= b[i]) 
	  		f[i][j + 1] = min(f[i][j + 1], f[i + 1][j] + a[i]);//dp
	  	}
	  }
	  for(int i = n; i >0 ; i--)
	  if(f[1][i] != u) 
	    {
	    	printf("%d", i);
			break;
	    }
		return 0;
}

T10：没有上司的晚会

思路：

这题用树形DP…
首先，上司和职员是这样的关系：
上司去了，职员必定不去。上司不去，职员可去可不去，然后我们就设
DP方程

//（dep 是 一个参数）
//f[dep][0]为上司不去，下属选择去或不去
//f[dep][1]为上司去，下属必定不去
	f[dep][0] += max(f[e[i].p][0],f[e[i].p][1]);
	f[dep][1] += f[e[i].p][0];	

C o d e Code Code:

#include <cstdio>
#include <iostream>
using namespace std;
int n,l,k,root;
int happy[100001],h[100001],f[100001][10];
bool jl[100001];
struct node
{
	int w,p,s;
}e[1000001];
void tree_DP (int dep)
{
	f[dep][1] = happy[dep];
	for(int i = h[dep]; i; i = e[i].s)
	{
	    tree_DP(e[i].p);
		f[dep][0] += max(f[e[i].p][0], f[e[i].p][1]);//dp
		f[dep][1] += f[e[i].p][0];		
	} 
}
int main ()
{
	scanf ("%d",&n);
	for (int i = 1; i <= n; ++i)
	    scanf("%d",&happy[i]);
	for (int i = 1; i <= (n - 1); ++i)
	{
		scanf ("%d%d", &l, &k);
		e[i].w = k,e[i].p = l,e[i].s = h[k],h[k] = i;
		jl[l] = true;
	}
	scanf("%d%d",&l,&k);
	for (int i = 1; i <= n; ++i)
	{
		if (jl[i] == false) 
		{
			root = i;
			break;
		}
	}
	tree_DP (root);
	printf ("%d", max(f[root][0],f[root][1]));
	return 0;
}

T11：分组背包：

思路：

三重循环枚举

C o d e Code Code:

#include<cstdio>
#include<iostream>
using namespace std;
int a[150][300],v[150][300],b[150],f[205],n,t,m,w,c,p;
int main()
{
	scanf("%d%d%d",&m,&n,&t);
	for (int i=1;i<=n;i++)
	  {
	  	scanf("%d%d%d",&w,&c,&p);
	  	v[p][++b[p]] = w;//记录
	  	a[p][b[p]] = c;
	  }
	for (int i = 1; i <= t; i++)
	  for (int j = m;j > 0; j--)
	    for (int k = 1; k <= b[i]; k++)
	      if (j >= v[i][k])
	        f[j] = max(f[j], f[j - v[i][k]] + a[i][k]);//dp
	printf("%d",f[m]);
	return 0;
}

T12：书的复制

思路：

正解二分
当然这题数据不是很大可以用 O ( n 2 ∗ k ) O(n^2*k) O(n2∗k)DP过

C o d e Code Code:

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,x,s[502],f[502][502];
int main()
{
	memset(f,127 / 3,sizeof(f));
  	scanf("%d%d",&n,&m);
  	for(int i = 1; i <= n; i++)
  	{
  	    scanf("%d",&x);
        s[i] = s[i - 1] + x;
        f[i][1] = s[i];
    }
    for (int k = 2; k <= m; k++)
	  for (int i = k; i <= n - m + k; i++)
	    for (int j = 1; j < i; j++)
           f[i][k] = min(f[i][k], max(f[j][k - 1], s[i] - s[j]));//dp

  printf("%d",f[n][m]);
  return 0;
}