Posted on 2010-08-26 21:38
Onway 閱讀(836)
評論(0) 編輯 收藏 引用 所屬分類:
傷不起的ACM
pku 1651 Multiplication Puzzle
題意：給出一組N個數(shù)，每次從中抽出一個數(shù)（第一和最后一個不能抽），該次的得分即為抽出的數(shù)與相鄰兩個數(shù)的乘積。直到只剩下首尾兩個數(shù)為止。問最小得分是多少。
最優(yōu)子結(jié)構(gòu)：
假設(shè)總得分最小時最后抽出的數(shù)在k位置，則在1:k和k:n之間的得分也是最小的。因為如果1:k或者k:n具有更小得分，則總得分會更小，與假設(shè)矛盾。
狀態(tài)設(shè)計：
設(shè)dp[i][j]為第i個數(shù)到第j個數(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;
}
這個題目折騰了我很久，估計也有五六個小時。可能是太久（也快半個月了）沒做過題，也可能是對矩陣連乘這類DP，或者直接是對DP沒有更深入的理解（其實真正領(lǐng)悟DP又何嘗簡單？可以原諒）。其實矩陣連乘，在前幾天才看了第二遍，當時沒看書上的代碼，認為對于DP看方程看代碼其實是沒多少意思的，重要的是那個思路，問題的分析，子結(jié)構(gòu)的證明，然后自己寫方程寫代碼。
我是百度矩陣連乘搜到這個題目的，所以這個題目的方法一開始就知道。最先自己簡單的分析了一下子結(jié)構(gòu)，然后找了個方程就開始寫遞歸，結(jié)果調(diào)試就卡住了。然后沒用遞歸，用數(shù)組，用堆棧又寫了兩次，發(fā)現(xiàn)都是卡在了同一個地方。
后來懷疑起子結(jié)構(gòu)和方程，原來對子結(jié)構(gòu)沒有搞清楚，寫出的方程也錯的很不靠譜。待我通過了這個題后，看回自己的DP方程，發(fā)現(xiàn)兜了一大圈，還真是回到了矩陣連乘這里。
對于一個方法已經(jīng)知道，類型也見過的題目，總是有一點輕視，加之對原來了解的就不深入，犯錯就很容易理解了。
最后說說編程上的知識：
1， memset,strlen等字符串處理函數(shù)在G++要用到<cstring>頭文件
2， scanf,printf要用到<stdio.h>頭文件
3， ；abs在<cstdlib>中；fabs，sin，sqrt等數(shù)學(xué)函數(shù)在<cmath>中