首页 > 代码库 > poj1651（区间dp）

poj1651（区间dp）

2024-11-25 03:42:02   204人阅读

 

题目连接：http://poj.org/problem?id=1651

题意：给出一组N个数，每次从中抽出一个数（第一和最后一个不能抽），该次的得分即为抽出的数与相邻两个数的乘积。直到只剩下首尾两个数为止。问最小得分？

分析：区间dp，记忆化搜索，dp[l][r]表示去掉l~r中所有数（不包括l、r）后得到的最小值，那么当前区间最小值为dp[l][r]=min(dp[l][r],dp[l][i]+dp[i][r]+a[l]*a[r]*a[i]).

技术分享
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int a[110],dp[110][110];int dfs(int l,int r){    if(dp[l][r]!=-1)return dp[l][r];    if(r-l<2)return 0;    int temp=inf;    for(int i=l+1;i<r;i++)        temp=min(dfs(l,i)+dfs(i,r)+a[i]*a[l]*a[r],temp);    return dp[l][r]=temp;}int main(){    int n;    while(scanf("%d",&n)>0)    {        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);        FILL(dp,-1);        printf("%d\n",dfs(1,n));    }}
View Code

 

poj1651（区间dp）


联系
我们