精华内容
下载资源
问答
  • 针对决策信息为区间直觉模糊数且属性权重完全未知的多属性决策问题, 提出基于改进的区间直觉模糊熵和新得分函数的决策方法. 首先, 利用改进的区间直觉模糊熵确定属性权重; 然后, 利用区间直觉模糊加权算术平均算子...
  • 叶值的最小代价生成树(区间DP/单调栈贪心) dp[i][j] 表示区间 [i,j] 所有组成的三角形得分之和的最小值 区间长度从 3 开始往上变大 状态转移方程为 dp[i][j]=min(dp[i][j],dp[i][k]+A[i]∗A[k]∗A[j]+dp[k][j])dp...

    文章目录

    1. 题目

    给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]

    假设您将多边形剖分为 N-2 个三角形。
    对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和

    返回多边形进行三角剖分后可以得到的最低分

    示例 1:
    输入:[1,2,3]
    输出:6
    解释:多边形已经三角化,唯一三角形的分数为 6
    示例 2

    在这里插入图片描述

    输入:[3,7,4,5]
    输出:144
    解释:有两种三角剖分,
    可能得分分别为:3*7*5 + 4*5*7 = 245,
    或 3*4*5 + 3*4*7 = 144。
    最低分数为 144。
    
    示例 3:
    输入:[1,3,1,4,1,5]
    输出:13
    解释:最低分数三角剖分的得分情况为 
    1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
     
    提示:
    3 <= A.length <= 50
    1 <= A[i] <= 100
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    2. 解题

    类似题目:
    LeetCode 1130. 叶值的最小代价生成树(区间DP/单调栈贪心)

    • dp[i][j] 表示区间 [i,j] 所有组成的三角形得分之和的最小值
    • 区间长度从 3 开始往上变大
    • 状态转移方程为 dp[i][j]=min(dp[i][j],dp[i][k]+A[i]A[k]A[j]+dp[k][j])dp[i][j] = min(dp[i][j], dp[i][k]+A[i]*A[k]*A[j]+dp[k][j])k 取值 [i+1, j-1]
    class Solution {
    public:
        int minScoreTriangulation(vector<int>& A) {
        	int n = A.size(), len, i, j, k;
        	vector<vector<int>> dp(n, vector<int>(n, 0));
        	for(len = 3; len <= n; ++len)
        	{
        		for(i = 0; i < n; ++i)
        		{
        			j = i+len-1;
        			if(j >= n) continue;
        			dp[i][j] = INT_MAX;
        			for(k = i+1; k < j; ++k)
        			{
        				dp[i][j] = min(dp[i][j], dp[i][k]+A[i]*A[k]*A[j]+dp[k][j]);
        			}
        		}
        	}
        	return dp[0][n-1];
        }
    };
    

    8 ms 8.8 MB


    我的CSDN博客地址 https://michael.blog.csdn.net/

    长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
    Michael阿明

    展开全文
  • 论文研究-基于区间直觉模糊数的得分函数与精确函数及其应用.pdf, 在模糊决策理论中,区间直觉模糊数的排序是一个非常重要的理论问题.运用得分函数和精确函数对区间直觉...
  • 多边形三角剖分的最低得分 解题思路:区间dp。对于任意的n边形,先算其中所有三角形的最优解,再算每个四边形的最优解…最后推到n边形就行了。 class Solution { public: int minScoreTriangulation(vector<int...

    leetcode1039.多边形三角剖分的最低得分

    解题思路:区间dp。对于任意的n边形,先算其中所有三角形的最优解,再算每个四边形的最优解…最后推到n边形就行了。
    在这里插入图片描述

    class Solution {
    public:
        int minScoreTriangulation(vector<int>& A) {
    		int dp[55][55];
    		memset(dp, 0, sizeof(dp));
    		int n = A.size();
    		for (int len = 3; len <= n; len++)
    		{
    			for (int i = 0; i + len - 1 < n; i++)
    			{
    				int j = i + len - 1;
    				dp[i][j] = INT_MAX;
    				for (int k = i + 1; k < j; k++)
    				{
    					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[j] * A[k]);
    				}
    			}
    		}
    		return dp[0][n - 1];
        }
    };
    
    展开全文
  • 1039. 多边形三角剖分的最低得分 分割一个凸多边形的方案数: 如何做到不重不漏? 如下图: 在剖分的最后,111和nnn一定会和第三个点构成一个三角形(如果不是,就不满足题目要求了), 在[2,n−1][2,n-1][2,n−1]中...

    1039. 多边形三角剖分的最低得分
    分割一个凸多边形的方案数:

    如何做到不重不漏?
    如下图:
    在剖分的最后,11nn一定会和第三个点构成一个三角形(如果不是,就不满足题目要求了),
    [2,n1][2,n-1]中枚举第三个点kk,构成一个三角形,剩下的[1,k][1,k][k,n][k,n]再次去划分,这就是相同结构的子问题了(当然也可能只有两个点,是基本情况)。
    有没有重复?没有,选择了k和1、n构成三角形,其他划分里就不会出现{1,n,k}\{1,n,k\}这个三角形了,同理,其他情况类似。

    于是方案数
    f[n]=k=2n1f[k]f[nk+1]f[n] = \sum_{k=2}^{n-1} f[k]*f[n-k+1]
    f[2]=1f[2] = 1
    则$f[3]=1,f[4]=2,f[5]=5……正是卡特兰数!

    在这里插入图片描述

    当然这道题并不是让我们计算划分的方案数,但是,状态转移的思路是一致的。
    dp[i][j]=min(a[i]a[k]a[j]+dp[i][k]+dp[k][j])dp[i][j] = min(a[i]*a[k]*a[j]+dp[i][k]+dp[k][j])

    class Solution {
    public:
        int n,dp[55][55] = {0};
        int minScoreTriangulation(vector<int>& A) {
            n = A.size();
            return dfs(0,n-1,A);    
        }
        long long dfs(int l,int r,const vector<int>& a){
            if(l+1==r) return 0;
            if(dp[l][r]) return dp[l][r];
            long long res = LLONG_MAX;
            for(int k=l+1;k<r;k++){
                res = min(res,a[l]*a[k]*a[r]+dfs(l,k,a)+dfs(k,r,a)); 
            }
            return dp[l][r] = res;
        }
    };
    
    展开全文
  • 一、Problem 给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。...解释:有两种三角剖分,可能得分分别为:3*7*5 + 4*5*7 = 245,或 3*4*5 + 3*4*7 = 144。最低分数为 144。

    一、Problem

    给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。

    假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

    返回多边形进行三角剖分后可以得到的最低分。
    在这里插入图片描述

    输入:[3,7,4,5]
    输出:144
    解释:有两种三角剖分,可能得分分别为:3*7*5 + 4*5*7 = 245,或 3*4*5 + 3*4*7 = 144。最低分数为 144。
    

    提示:

    3 <= A.length <= 50
    1 <= A[i] <= 100

    二、Solution

    方法一:dp

    思路

    怎么才能让所有三角形的点乘积和最小呢?一个比较直观的出发点就是:将大的数分开,尽量避免让它被「共享」 ,就比如说上图的顶点 7,图二就避免了「共享」 ,但哪些点被共享和不被共享是我们无法事先确定的,所以我们只能通过枚举且取枚举结果的最小得分情况。

    算法

    在这里插入图片描述

    • 定义状态
      • f[i][j]f[i][j] 表示将第 ii 个角到第 jj 个角所组成将 n 边形分成 n-2 个三角形的最低得分
    • 思考初始化:
      • f[0:][0:]=INFf[0:][0:] = INF
    • 思考状态转移方程
      • f[i][j]=min(f[i][j], f[i][k]+f[k][j]+A[i]×A[j]×A[k])f[i][j] = min(f[i][j],\ f[i][k] +f[k][j] + A[i] × A[j] × A[k]) 表示不断枚举将序列 A[i:j]A[i:j] 分解成若干三角形的得分,取其中的最小得分
    • 思考输出f[0][n1]f[0][n-1]
    class Solution {
        public int minScoreTriangulation(int[] A) {
        	int n = A.length, INF = 0x3f3f3f3f, f[][] = new int[n][n];
    
        	for (int l = 2; l < n; l++)
    		for (int i = 0; i < n-l; i++) {
    			int j = i + l;
    			f[i][j] = INF;
    			for (int k = i+1; k < j; k++) {
    				f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + A[i]*A[j]*A[k]);
    			}
    		}
    		return f[0][n-1];
        }
    }
    

    复杂度分析

    • 时间复杂度:O(n3)O(n^3)
    • 空间复杂度:O(n2)O(n^2)
    展开全文
  • 本题就是在区间DP的基础上确定了增加一维来表示右边拼上一些方块得到的最大得分 区间DP的解决,使用记忆化搜索比DP更加简单且不易出错,就按照LRJ的模型学习掌握即可 #include <set> #include <map> #...
  • 区间dp

    2019-09-24 14:23:42
    上一篇文章求得每一块...有一个长度为n的整数序列,A和B轮流取数,A先取,每次可以从左端或者右端取一个数,所有数都被取完时游戏结束,然后统计每个人取走的所有数字之和作为得分,两人的策略都是使自己的得分尽可...
  • 区间DP

    2017-10-30 18:15:30
    怎么合并的总得分最大呢,就要保证每一次合并后,得分都最大。符合最优性原则,可以用我们神奇的DP做。 这道题目就是典型的一个区间DP。我们可以知道,每一个区间的最优解都是由更小的区间的最
  • 文章目录 题目分析 题目链接 题目分析 1。数组中没有负数意味着什么?意味着区间越大,其和越大。 2. 对于给定下标i,其左边的一个区间满足没有重复数的左边界(最左边)下标为j,我们有,随着... 删除子数组的最大得分
  • 威尔逊区间

    千次阅读 2017-12-20 19:47:17
    由于工作原因要使用威尔逊区间来计算POI与TD之间的分数,现在总结一下。 对于召回的一些数据如何给这些数据来排名,然后根据这个排名来显示数据,这就需要使用“威尔逊区间”了。 首先我们讨论的情况是每个项目...
  • 区间DP总结

    2020-07-06 10:31:23
    序列是一个链(非环),求从区间(l,r)之间的最大得分,典型问题:石子数问题。 f(l,r)表示把第l堆到第r堆的石子合并在一起的最大得分,最后合并在一堆的石子来源于前两堆,其中一堆在(l,k),另一堆在(k+1,r)区间内...
  • 区间型DP

    2016-11-13 23:09:00
    区间型DP是一类经典的动态规划问题,主要特征是可以先将大区间拆分成小区间求解最后由小区间的解得到大区间的解。 有三道例题 一、石子合并 在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定...
  • 区间DP训练

    2018-08-24 19:24:00
    区间DP训练 一、石子合并 问题描述 将 n (\(1 \le n \le 200\))堆石子绕圆形操场摆放,现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次...
  • 区间动态规划

    2017-07-18 19:34:00
    现在有n块石头,多多要把这n个石头进行合并每一次合并,多多可以把相邻两个石子合并到一起,得分等于两个石头的重量之和。 可以看出,所有的石子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共的得分...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 711
精华内容 284
关键字:

得分区间