uva 11400 lrj-P275 动态规划

el/2024/2/25 22:20:31

题意:

见刘汝佳入门书籍 P275

dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*a[i].c+a[i].k);
题解:

见刘汝佳入门书籍 P275


#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int dp[1010],sum[1010];
struct Lamp
{int v, k, c, l;bool operator < (const Lamp& rhs) const {return v < rhs.v;}
}a[1010];int main()
{int n;//freopen("in.txt","r",stdin);while(scanf("%d",&n),n){for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].v,&a[i].k,&a[i].c,&a[i].l);sort(a+1,a+1+n);sum[0]=0;for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].l;dp[0]=0;for(int i=1;i<=n;i++) {dp[i]=sum[i]*a[i].c+a[i].k;for(int j=0;j<i;j++) {dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*a[i].c+a[i].k);}}printf("%d\n",dp[n]);}return 0;
}



http://www.ngui.cc/el/4895175.html

相关文章

密码生成器+随机数生成器

随机数生成器 0~RAND_MAX之间的随机数程序 #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; int main() {srand((unsigned)time(NULL));for(int i = 0; i < 10; i++ )cout << rand() << \t;cout << …

uva 10003 lrj-P278 区间dp入门

题意&#xff1a; 给出一根棍子的长度&#xff0c;以及n个需要切割的点&#xff0c;每一次切割的代价是这一段需要被切割的长度 问代价最小时的代价值 题解&#xff1a; 区间dp dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]a[j]-a[i]); i 为区间左端点&#xff0c;j 为右端点…

Uva-1626 lrj-P278 区间dp

题意&#xff1a; 给定一个由[,],(,)&#xff0c;构成的字符串&#xff0c;给其添加这些括号使得其成为一个正规括号序列 1 空序列是正规括号序列 2 如果S是正规括号序列&#xff0c;那么[S]和(S)也是正规括号序列 3 如果A和B都是正规括号序列&#xff0c;则AB也是正规…

uva 1331 lrj-P279 三角剖分+区间dp

题意&#xff1a; 给出多边形&#xff0c;找出最大三角形面积最小的三角剖分 输出最大的三角形面积 题解&#xff1a; 仔细研究可以知道&#xff0c;第一个点和最后一个点组成的边&#xff0c;一定是在某一个三角形中 那么我们就通过这个边作为基准&#xff0c;任选一个…

uva 12186 lrj-P282 简单树形dp

题意&#xff1a; 某个人签字的话,他的直属下属里必须有至少T%的人签字,问让老板签字最少需要多少工人签字 题解&#xff1a; 树形dp 以老板为根节点&#xff0c;从小往上&#xff0c;递归计算答案即可 #include<vector> #include<stdio.h> #include<st…

uva 1220 lrj-P282 最大独立集(树形dp)

题意&#xff1a; 给出一个树形结构&#xff0c;除了老板外&#xff0c;每一个员工都有直属上司&#xff0c;在其中挑选了员工&#xff0c;就不能挑选他的上司 问这样的挑选方法最多可以挑选多少人&#xff0c;方案是否唯一 题解&#xff1a; 仔细划分即可 当前节点若选…

uva 10285 lrj-P304 从简单DAG动态规划得到的感悟

题意&#xff1a; 给出一个整数矩阵&#xff0c;请找出一条严格递减的最长路的长度 题解&#xff1a; 分析&#xff1a; 1没有固定起点和终点 2是二元关系&#xff0c;也就是DAG&#xff08;有向无环图&#xff09; 3lrj书上此类一律都是用记忆化搜索 假设&#xff…

uva 1630 lrj-P305 字符串dp(记忆化)

题意&#xff1a; 给出一个字符串&#xff0c;然后要你把他折叠成一个最短的字符串 例如 AAAAAAAAAABABABCCD NEERCYESYESYESNEERCYESYESYES 变成&#xff1a; 9(A)3(AB)CCD 2(NEERC3(YES) 题解&#xff1a; 很容易看出来用分治的办法&#xff0c;但是不会把折叠起来&a…

hdu 6206 模板题 2017 ACM/ICPC Asia Regional Qingdao Online

下面的模板来自于 http://blog.csdn.net/liyuanbhu/article/details/52891868 三点确定一个圆的计算方法 最近在写的一个软件需要根据三个坐标点来计算一个圆。因此花了点时间推导了相关的公式。这个推导不算太难&#xff0c;放在这里主要是做个备忘。 我们设一个圆的圆…

uva 11582 lrj-P316 斐波那契大数

给出无符号64位的a b两个数&#xff0c;要求斐波那契数列中第a的b次方个数是多少&#xff1f;&#xff08;此数对n取模&#xff09; 取模运算a^b%n(a%n)^b&#xff0c;运用快速幂搞一手就好了 然后这里需要注意的是无符号输入的格式问题&#xff0c;见代码&#xff0c;以及n为…