hdu 3506 Monkey Party(區間dp+四邊形優化)

石子合并：有N堆石子，現要将石子有序的合并成一堆，規定如下：每次隻能移動相鄰的2堆石子合并，合并花費為新合成的一堆石子的數量。求将這N堆石子合并成一堆的總花費最小（或最大）。

為什麼用區間dp我就不解釋了，不懂的話網上有很多資料。

現在我來提醒一下寫這個dp要注意的問題

1.初态的設定

for(i=1;i<=m;i++)
  {
   for(j=1;j<=m;j++)
   {
    dp[i][j]=INF;
   }
  }
  for(i=1;i<=m;i++)
  {
   dp[i][i]=0; 
  }
           

2.動态方程轉移過程

for(len=2;len<=m;len++)//len表示石子堆長度，石子堆最少為兩堆，最多為m堆 
  {
   for(i=1;i+len-1<=m;i++)//i表示起點，i從1到m-len+1 
   {
    j=i+len-1;
    for(k=i;k<j;k++)//k為什麼不能等于j,卻能等于i,因為k=i時 表示第一堆和之後的所有的組成的堆一種情況，而k=j無意義 
    {
     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); 
    }
   }
  }
           

注意每一個變量的含義和取值範圍的理由

接下來給一個簡單版的石子合并

#include<iostream>
#define N 1000
#define INF 100000000
using namespace std;
int a[N];
int dp[N][N];
int sum[N];
int main()
{
 int n;
 cin>>n;
 while(n--)
 {
  int m,i,j,k,len;
  cin>>m;
  int total=0;
  sum[0]=0;
  for(i=1;i<=m;i++)
  {
   cin>>a[i];
   total+=a[i];
   sum[i]=total;
  }
  for(i=1;i<=m;i++)
  {
   for(j=1;j<=m;j++)
   {
    dp[i][j]=INF;
   }
  }
  for(i=1;i<=m;i++)
  {
   dp[i][i]=0; 
  }
  for(len=2;len<=m;len++)//len表示石子堆長度，石子堆最少為兩堆，最多為m堆 
  {
   for(i=1;i+len-1<=m;i++)//i表示起點，i從1到m-len+1 
   {
    j=i+len-1;
    for(k=i;k<j;k++)//k為什麼不能等于j,卻能等于i,因為k=i時 表示第一堆和之後的所有的組成的堆一種情況，而k=j無意義 
    {
     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); 
    }
   }
  }
  cout<<dp[1][m]<<endl;
 }
}
           

進階版：環形先變成線性的+四邊形優化

Monkey PartyTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 4515 Accepted Submission(s): 1662

Problem Description Far away from our world, there is a banana forest. And many lovely monkeys live there. One day, SDH(Song Da Hou), who is the king of banana forest, decides to hold a big party to celebrate Crazy Bananas Day. But the little monkeys don’t know each other, so as the king, SDH must do something.

Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are:

1.every time, he can only introduce one monkey and one of this monkey’s neighbor.

2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows;

3.each little monkey knows himself;

In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing.

Input There is several test cases. In each case, the first line is n(1 ≤ n ≤ 1000), which is the number of monkeys. The next line contains n positive integers(less than 1000), means the making friends time(in order, the first one and the last one are neighbors). The input is end of file.

Output For each case, you should print a line giving the mininal time SDH needs on introducing.

Sample Input8

5 2 4 7 6 1 3 9

Sample Output105

#include<iostream>
#include<cstdio>
#define N 2000
#define INF 100000000
using namespace std;
int a[N];
int dp[N][N];
int sum[N];
int s[N][N]; 
int main()
{ 
 int m,i,j,k,len;
 while(~scanf("%d",&m))//
 {
  int total=0;
  sum[0]=0;
  for(i=1;i<=m;i++)
  {
   scanf("%d",&a[i]);
   total+=a[i];
   sum[i]=total;
  }
  for(i=m+1;i<=2*m;i++)
  {
   a[i]=a[i-m];
   total+=a[i];
   sum[i]=total;
  }
  for(i=1;i<=2*m;i++)
  {
   dp[i][i]=0; 
   s[i][i]=i;
  }
  for(len=2;len<=2*m;len++)//len表示石子堆長度，石子堆最少為兩堆，最多為2*m堆 
  {
   for(i=1;i+len-1<=2*m;i++)//i表示起點，i從1到2*m-len+1 
   {
    j=i+len-1;
    dp[i][j]=INF;
    for(k=s[i][j-1];k<=s[i+1][j];k++)//k為什麼不能等于j,卻能等于i,因為k=i時 表示第一堆和之後的所有的組成的堆一種情況，而k=j無意義 
    {
     //dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); 
     if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]<dp[i][j])//我也不太明白為什麼 
     {
      dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
      s[i][j]=k;
     }
    }
    
   }
  }
  int mm=INF;
  for(i=1;i<=m;i++)
  {
   if(dp[i][i+m-1]<mm)
   mm=dp[i][i+m-1];
  }
  printf("%d\n",mm);
 }
}
 
           

在寫這個的過程中遇到了一個很基礎的問題

就是scanf前面為什麼要加~，關于這個問題，可以看以下一篇部落格scanf是什麼意思，為什麼scanf前加