pku 1651 Multiplication Puzzle
題意：給出一組N個(gè)數(shù)，每次從中抽出一個(gè)數(shù)（第一和最后一個(gè)不能抽），該次的得分即為抽出的數(shù)與相鄰兩個(gè)數(shù)的乘積。直到只剩下首尾兩個(gè)數(shù)為止。問(wèn)最小得分是多少。
最優(yōu)子結(jié)構(gòu)：
假設(shè)總得分最小時(shí)最后抽出的數(shù)在k位置，則在1:k和k:n之間的得分也是最小的。因?yàn)槿绻?:k或者k:n具有更小得分，則總得分會(huì)更小，與假設(shè)矛盾。
狀態(tài)設(shè)計(jì)：
設(shè)dp[i][j]為第i個(gè)數(shù)到第j個(gè)數(shù)的最小得分，則dp[1][n]即為題中的解。
1<=i<=n-2;i+2<=j<=n;
dp方程：
dp[i][j]=min(dp[i][k]+dp[k][j]+s[i]*s[k]*s[j]);i<k<j;
觀察方程，第一維中依賴的是i以后的值，第二維依賴的是j之前的值，所以第一維循環(huán)采用逆序循環(huán)，第二維采用順序循環(huán)。
| Memory: 756K |
|
Time: 0MS |
| Language: G++ |
|
Result: Accepted |
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int dp[103][103],s[103];
int main()
{
int n,i,j,k,min;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",&s[i]);
memset(dp,0,sizeof(dp));
for(i=n-2;i>=1;--i)
for(j=i+2;j<=n;++j)
{
min=i+1;
for(k=i+2;k<=j-1;++k)
if((dp[i][k]+dp[k][j]+s[i]*s[j]*s[k])<(dp[i][min]+dp[min][j]+
s[i]*s[j]*s[min]))
min=k;
dp[i][j]=dp[i][min]+dp[min][j]+s[i]*s[j]*s[min];
}
cout<<dp[1][n]<<endl;
return 0;
}
這個(gè)題目折騰了我很久，估計(jì)也有五六個(gè)小時(shí)。可能是太久（也快半個(gè)月了）沒(méi)做過(guò)題，也可能是對(duì)矩陣連乘這類DP，或者直接是對(duì)DP沒(méi)有更深入的理解（其實(shí)真正領(lǐng)悟DP又何嘗簡(jiǎn)單？可以原諒）。其實(shí)矩陣連乘，在前幾天才看了第二遍，當(dāng)時(shí)沒(méi)看書上的代碼，認(rèn)為對(duì)于DP看方程看代碼其實(shí)是沒(méi)多少意思的，重要的是那個(gè)思路，問(wèn)題的分析，子結(jié)構(gòu)的證明，然后自己寫方程寫代碼。
我是百度矩陣連乘搜到這個(gè)題目的，所以這個(gè)題目的方法一開(kāi)始就知道。最先自己簡(jiǎn)單的分析了一下子結(jié)構(gòu)，然后找了個(gè)方程就開(kāi)始寫遞歸，結(jié)果調(diào)試就卡住了。然后沒(méi)用遞歸，用數(shù)組，用堆棧又寫了兩次，發(fā)現(xiàn)都是卡在了同一個(gè)地方。
后來(lái)懷疑起子結(jié)構(gòu)和方程，原來(lái)對(duì)子結(jié)構(gòu)沒(méi)有搞清楚，寫出的方程也錯(cuò)的很不靠譜。待我通過(guò)了這個(gè)題后，看回自己的DP方程，發(fā)現(xiàn)兜了一大圈，還真是回到了矩陣連乘這里。
對(duì)于一個(gè)方法已經(jīng)知道，類型也見(jiàn)過(guò)的題目，總是有一點(diǎn)輕視，加之對(duì)原來(lái)了解的就不深入，犯錯(cuò)就很容易理解了。
最后說(shuō)說(shuō)編程上的知識(shí)：
1， memset,strlen等字符串處理函數(shù)在G++要用到<cstring>頭文件
2， scanf,printf要用到<stdio.h>頭文件
3， ；abs在<cstdlib>中；fabs，sin，sqrt等數(shù)學(xué)函數(shù)在<cmath>中