River Crossing 简单的动态规划 .-白红宇

River Crossing 简单的动态规划 .

阅读量：6409 次

发布时间：2019-06-23

本文共 925 字，大约阅读时间需要 3 分钟。

第一行 t 表示有几组测试数据 .

每组测试数据的第一行是 n, m . 然后下面有n行数据 .

题意：有1个人和N只羊要过河。一个人单独过河花费的时间是M，每次带一只羊过河花费时间M+M1，带两只羊过河花费时间M+M1+M2……给出N、M和Mi，问N只羊全部过河最少花费的时间是多少。

　　相当于 , 羊都是一样的 , 但是羊数量的不同 , 导致该羊在船上的增加水阻力的大小也不同 , Mi 是不论那只羊 , 只要数量是 i 那么该羊在船上就增加了 Mi 个阻力 .

理解了题意 , 接下来就是状态转移了.

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                13 #include
                 
                  14 #include
                  
                   15 using namespace std;16 int dp[1005],time1[1005];17 int main()18 {19 int t,n,m;20 scanf("%d",&t);21 while(t--)22 {23 scanf("%d%d",&n,&m);24 for(int i=1;i<=n;i++)25 {26 scanf("%d",&time1[i]);27 time1[i]=time1[i]+time1[i-1]; // 这也算是 惯用手段了 . 28 }29 for(int i=1;i<=n;i++)30 {31 dp[i]=time1[i]+m; // 默认一下 , 前 i 只羊的最短用时 32 for(int j=1;j