蓝桥杯 试题 算法提高 宰羊 DP解决

问题描述

　　炫炫回了内蒙，肯定要吃羊肉啦，所有他家要宰羊吃。
　　炫炫家有N只羊，羊圈排成一排，标号1~N。炫炫每天吃掉一只羊（这食量！其实是放生啦），吃掉的羊的邻居会以为它被放生了，然后又会告诉他们的邻居，这样一直传播下去，除非某个邻居已经被“放生”了。每一天，所有知道某羊被“放生”了这个消息的羊都会很不满，如果不给他们巧克力的话，他们就会很*，炫炫已经知道他要吃掉哪些羊，他可以任意安排吃的顺序，然后使巧克力的用量最小，请求出这个最小值。

输入格式

　　本题有多组数据，第一行为数据组数T。
　　对于每组数据
　　第一行：两个用空格隔开的整数：N和M，表示羊的数量和需要吃掉的数量
　　第二行：有M个数，表示要吃那些羊。

输出格式

　　T行，为每组数据的答案。

样例输入

2
8 1
3
20 3
3 6 14

样例输出

7
35

---

解题思路：解这道题的关键是，当放生(或吃掉)一个位置的羊后，此位置的左端和右端就相互独立了，即原问题变成了两个规模更小独立的子问题。要求原问题的最优解，则其子问题也必须是最优。(可以

用"剪切-粘贴"("cut-and-paste")技术证明，即如果子问题的解如果不是最优，则可以选择其最优解代替非最优解(剪切非最优解，粘贴最优解) )。所以此题可以用DP解决。

释放K位置羊所需的巧克力数：

　　•此时所需的巧克力数

　　•释放位置左侧所需巧克力数　　

　　•释放位置右侧所需巧克力数

设数组A[]保存要被放生羊的位置，dp[ i ][ j ]：将A[ i ] 到 A[ j ] 连续部分的羊都放生后所需最小巧克力数。dp[ i ] [ j ]  = min( dp[ i ][ j ] , dp[ i ][ k ] + dp[ k ][ j ] ), dp[ i ][ j ] +=  A[ j ] - A[ i ] - 2

 

//完整代码

 #include<cstdio>
 #include<climits>//INT_MAX
 #include<algorithm>
 using namespace std;

 const int Max_M = ;

 //输入
 int T,N,M;
 int A[Max_M+]; //A下标: 0 - M+1 保存要吃掉羊的位置 

 int dp[Max_M+][Max_M+];//i:0-M j:0-M+1 dp数组 

 void solve()
 {
     A[] = ; //因为dp[i][j]不包含两端，所以为统一求解
     A[M+] = N+;//最后答案即 dp[0][N+1] 所以额外加上这两个位置

     //初始化dp数组
     for(int m=; m<=M; m++){
         dp[m][m+] = ;
     } 

     //从短区间开始填充dp数组 w:区间长度
     for(int w=; w<=M+; w++)
     {
         for(int i=; i+w<=M+; i++ )// j <= M+1
         {
             int j = i + w;
             int t = INT_MAX;
             for(int k=i+; k<j; k++){
                 t = min( t, dp[i][k]+dp[k][j]);
             }
             dp[i][j] = t + A[j] - A[i] - ;
         }
     }
     printf("%d\n",dp[][M+]);
 }

 int main()
 {
     scanf("%d",&T);
     while( T-- )
     {
         scanf("%d%d",&N,&M);
         for(int i=; i<=M; i++){
             scanf("%d",&A[i]);
         }

         solve();
     }

     return ;
 }