首页 > 代码库 > HDU_4960 2014多校9 Another OCD Patient DP

HDU_4960 2014多校9 Another OCD Patient DP

2024-07-19 05:34:20   215人阅读

其实现在想起来是个巨简单的DP，模型就跟LCS很像，比赛的时候居然没想出来，在聪哥提醒下还卡了个地方

就是说给定一串n个数字的序列，可以连续合并，最终使得序列是回文的，题目也给定了合并数字所需的代价，合并一个为0，合并2个 3个。。n个的代价都有

题目比较新意的地方就是回文，这也是我们要解决的主要地方，回文。。其实用前缀和+后缀和就可以解决了。。。

用记忆化搜索写起来比较方便，每次对于求的L和R，枚举i,j，使得 L-i合并之后可以与j-R合并之后回文，然后递归处理i和j即可。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL __int64using namespace std;LL pre[5010];int A[5010];int n;int dp[5010][5010];int dfs(int l,int r){    if (l>r) return 0;    if (dp[l][r]!=-1) return dp[l][r];    dp[l][r]=A[r-l+1];    int p=l,q=r;    for (p=l,q=r;p<q;)    {        if ((pre[p]-pre[l-1])<(pre[r]-pre[q-1])){            p++;continue;        }        if ((pre[p]-pre[l-1])>(pre[r]-pre[q-1])){            q--;continue;        }        if ((pre[p]-pre[l-1])==(pre[r]-pre[q-1])){            dp[l][r]=min(dp[l][r],A[p-l+1]+dfs(p+1,q-1)+A[r-q+1]);            p++;        }    }    return dp[l][r];}int main(){   while (scanf("%d",&n)!=EOF)   {       if (n==0) break;       for (int i=1;i<=n;i++){         scanf("%I64d",&pre[i]);         pre[i]+=pre[i-1];         for (int j=1;j<=n;j++) dp[i][j]=-1;       }       for (int i=1;i<=n;i++) scanf("%d",&A[i]);       printf("%d\n",dfs(1,n));   }   return 0;}

　　

HDU_4960 2014多校9 Another OCD Patient DP


联系
我们