-
POJ 2976最简单的 01分数规划
2018-08-03 10:20:37二分法(二分一个mid看是否存在这样的一组解,不断缩小区间逼近最优值) #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> ...题目:给出n个a和b,让选出n-k个使得
最大 。
二分法(二分一个mid看是否存在这样的一组解,不断缩小区间逼近最优值)
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; #define eps 1e-6 #define inf 1e12 const int maxn=1010; int n,k; int a[maxn],b[maxn]; double y[maxn]; bool check(double x) { for(int i=1;i<=n;i++) y[i]=a[i]-b[i]*x; sort(y+1,y+n+1); double sum=0; for(int i=1;i<=k;i++) sum+=y[n-i+1]; return sum>0; } void solve() { double l=0,r=inf; while(r-l>eps) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.0f\n",l*100.0); } int main() { while(~scanf("%d%d",&n,&k)) { if(n+k==0) break; k=n-k; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); solve(); } return 0; }
Dinkelbach算法 (本质是一种迭代算法,基于这样的思想:不去二分答案,而是先随便给定一个答案,然后根据更优的解不断移动答案,逼近最优解。理论上它比二分快些。 在这个算法中,一般将ans初始化为0)
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; #define eps 1e-6 #define inf 1e12 const int maxn=1010; struct node{ int a,b; double y; }s[maxn]; bool cmp(const node &a,const node &b) { return a.y>b.y; } int n,k; double Dinkelbach() { double ans=0,x=0,U,D; while(1) { x=ans; for(int i=1;i<=n;i++) s[i].y=s[i].a-s[i].b*x; sort(s+1,s+n+1,cmp); U=D=0; for(int i=1;i<=k;i++) { U+=1.0*s[i].a; D+=1.0*s[i].b; } ans=U/D; if(fabs(ans-x)<eps) return ans; } } int main() { while(~scanf("%d%d",&n,&k)) { if(n+k==0) break; k=n-k; for(int i=1;i<=n;i++) scanf("%d",&s[i].a); for(int i=1;i<=n;i++) scanf("%d",&s[i].b); printf("%.0f\n",Dinkelbach()*100.0); } return 0; }
-
hrbust1818 石子合并问题--直线版 (经典区间DP)
2013-08-15 00:38:00求解的大问题是在区间[1, n]内合并石子的最优值,石子分成两个区间[1,k][k+1,n]。不断地将大区间分成小区间。 设dpmax[i][j]表示i堆石子到j堆石子合并得到的最大分数,dpmin[i][j]表示i堆石子到j堆石子合并得到的...求解的大问题是在区间[1, n]内合并石子的最优值,石子分成两个区间[1,k][k+1,n]。不断地将大区间分成小区间。
设dpmax[i][j]表示i堆石子到j堆石子合并得到的最大分数,dpmin[i][j]表示i堆石子到j堆石子合并得到的大小分数,num[i][j]表示i堆石子到j堆石子的总数
状态转移方程:
dpmax[i][j]=max{dp[i][k]+dp[k+1][j]+num[i][j]} k在区间[i, j-1]内
dpmin[i][j]=min{dp[i][k]+dp[k+1][j]+num[i][j]} k在区间[i, j-1]内
3.初始化:dpmax[i][i]=0;dpmin[i][j]=0;就是说一堆石子没办法和相邻的石子合并#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define clr(x) memset(x,0,sizeof(x)) #define INF 0x1f1f1f1f long long fmax[105][105]; long long fmin[105][105]; long long a[105]; long long sum[105]; long long num[105][105]; int n,i,j,len,k; int main(){ while(scanf("%d",&n)!=EOF){ clr(sum); clr(fmax); memset(fmin,INF,sizeof(fmin)); int tot=0; for(i=1;i<=n;i++){ scanf("%lld",&a[i]); tot=tot+a[i]; sum[i]=tot; } for(i=1;i<=n;i++) for(j=i;j<=n;j++){ num[i][j]=sum[j]-sum[i-1]; } //f[i][j]=f[i+k]+f[k+1][j]+num[i][j] for(i=1;i<=n;i++) fmin[i][i]=0,fmax[i][i]=0; for(len=1;len<n;len++){ for(i=1;i<=n-len;i++){ j=i+len; for(k=i;k<j;k++){ fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+num[i][j]); fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+num[i][j]); } } } printf("%lld %lld\n",fmin[1][n],fmax[1][n]); } return 0; }
-
洛谷P1040 加分二叉树运用区间DP(动态规划)求解
2020-02-11 21:51:11而且每次求出的解不是独立的,我们需要逐层推出最优解。 二、以这道题为例,题目要求整棵二叉树加分最大,并且分数=左子树分数* 右子树分数+自身数值,这就需要使左右子树分数尽可能大->左右子树的子树要大,所以...首先放上原题链接
什么是动态规划?
在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。而且每次求出的解不是独立的,我们需要逐层推出最优解。
以这道题为例,题目要求整棵二叉树加分最大,并且分数=左子树分数* 右子树分数+自身数值,这就需要使左右子树分数尽可能大->左右子树的子树要大,所以我们就需要选取一个合适的根节点。并且求出此时的最大分数。求解过程
接着就是求解动态规划的状态转移方程了。
我们其实就可以将题目看做求[i,j]这个区间里的最大值,这样就可以得出状态转移方程f[i][j]=max{f[i][k-1]*f[k+1][j]+f[k][k] | i<=k<=j}//i,j是区间范围,k为根节点
题目还要求先序遍历输出,所以我们还需要一个root[i][j]数组来表示节点i到节点j成树的最大加分所选的根节点。
下面上代码进行分析
#include <iostream> using namespace std; long long n; long long f[100][100],root[100][100];//创建所需要的f和root数组 void xianxu(long long ,long long );//先序遍历的函数 int main() { int i,len,j; cin>>n; for(i=1;i<=n;i++)//因为中序遍历从1开始的,所以从1开始有很好的对应性 { cin>>f[i][i];//将分数值存储到相应的f里 root[i][i]=i;//中序的遍历的数据 } for(len=1;len<n;len++) { for(i=1;i+len<=n;i++)//多次取范围,求取符合f[i][k-1]*f[k+1][j]+f[k][k]最大的情况 { j=i+len;//范围的右边界 f[i][j]=f[i+1][j]+f[i][i];//易知当有左子树时,不会是最优解,所以最大值先先赋值为根+右子树的分数 root[i][j]=i;//默认设置根为第一个值 for(int k=i+1;k<j;k++)//当根为第二个,第三个……直到范围边界 { if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k])//计算当前取的根的情况下,f[i][j]是否为当前的最大值 { f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];//如果是,f[i][j]里的最大值就赋值 root[i][j]=k;//记录取最大值时的根 } } } } cout<<f[1][n]<<endl;//输出题目要求的[1,n]的最大值 xianxu(1,n);//进行先序遍历 return 0; } void xianxu(long long l,long long r) { if(l>r)//当左边比右边大时,进行回溯 { return; } cout<<root[l][r]<<" ";//输出先序遍历输出 if(l==r)//左右相等时回溯 { return; } xianxu(l,root[l][r]-1);//遍历左子树 xianxu(root[l][r]+1,r);//遍历右子树 }
至此完结
-
[BZOJ1758][WC2010]重建计划(01分数规划+点分治+单调队列)
2018-05-06 08:34:00二分mid,如果有更优的值∑(a−mid)>0∑(a−mid)>0\sum (a-mid)>0,那么我们的check途径就是通过点分治判断长度在[l,r]区间内有没有一条链的和>0,链的长度为a[i]-mid 而check的过程中...题目:
题解:
首先平均数最大,平均数其实是,求最值是01分数规划的问题
二分mid,如果有更优的值,那么我们的check途径就是通过点分治判断长度在[l,r]区间内有没有一条链的和>0,链的长度为a[i]-mid而check的过程中对于每个当前子树,维护每个深度的最优值,我们只需要取之前记录的最优的一项更新就好了。我们可以把当前子树中的值按深度从大到小来更新答案,这个过程中使用单调队列维护一个深度下降权值序列,然后每次取队首更新答案即可,每次查看队首的时候把已经相加超过R的踢出去,然后查看队尾,如果比这次要添加的L-j(即下限)更小的话就T出去
这个过程是线性的,而对于全部子树 i 深度最长距离的数组的更新也只是取个max,它也是线性的。
这题已经调的我不想写题解了,只能说ljBZOJ
代码:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N=150005; #define INF 1e9 int tot,nxt[N*2],L,R,point[N],v[N*2],f[N],size[N],root,sum,deep[N],DEP,dep,q[N]; double c[N*2],a[N],b[N],mid,ans;bool vis[N]; int read() { char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x; } void addline(int x,int y,double z) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z; } void getroot(int x,int fa) { f[x]=0; size[x]=1; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa && !vis[v[i]]) { getroot(v[i],x); size[x]+=size[v[i]]; f[x]=max(f[x],size[v[i]]); } f[x]=max(f[x],sum-size[x]); if (f[x]<f[root]) root=x; } void getdeep(int x,int fa) { deep[x]=deep[fa]+1; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa && !vis[v[i]]) getdeep(v[i],x); DEP=max(DEP,deep[x]); } void dfs(int x,int fa,double sum) { if (deep[x]>R) return; a[deep[x]]=max(a[deep[x]],sum); for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]] && v[i]!=fa) dfs(v[i],x,sum+c[i]-mid); dep=max(dep,deep[x]); } bool check() { double maxx=-INF;int now=0; b[0]=0; for (int i=1;i<=DEP;i++) b[i]=-INF; for (int i=point[root];i;i=nxt[i]) if (!vis[v[i]]) { int l=1,r=0;dep=0;a[0]=0; for (int j=1;j<=DEP;j++) a[j]=-INF; dfs(v[i],root,c[i]-mid); if (now) q[++r]=now; for (int j=1;j<=dep;j++) { if (j>R) break; while (l<=r && q[l]+j>R) l++; if (j<=L && L-j<=DEP) { while (l<=r && b[q[r]]<b[L-j]) r--; q[++r]=L-j; maxx=max(maxx,b[q[l]]+a[j]); }else if (j>L) maxx=max(maxx,b[q[l]]+a[j]); } for (int j=1;j<=dep;j++) { b[j]=max(b[j],a[j]); if (j>=L && j<=R && b[now]<b[j]) now=j; } } return maxx>0; } void work() { DEP=0;//// getdeep(root,0); double l=ans,r=1e6; while (r-l>1e-4) { mid=(l+r)/2; if (check()) l=mid;else r=mid; } vis[root]=1;ans=l; for (int i=point[root];i;i=nxt[i]) if (!vis[v[i]]) { sum=size[v[i]]; if (sum<L) continue; root=0; f[0]=INF; getroot(v[i],0); work(); } } int main() { int n;n=read();L=read();R=read(); for (int i=1;i<n;i++) { int x,y,z;x=read();y=read();z=read(); addline(x,y,z); } deep[0]=-1; sum=n; root=0; f[0]=INF; getroot(1,0); work(); printf("%.3lf",ans); }
-
佳佳的魔杖 (vijos 1283)
2019-10-08 15:02:51一根树枝有N段,每一段有一个分数,可以选取一些不完全包含(可以相交)的区间,每次选取可以得到区间里所有数之和的分数。求最大得分。 解题过程: 1.很明显的dp,默认选取区间的顺序是从左往右,F[i][j]表示... -
数据结构——赫夫曼树
2020-02-17 10:01:39比如要为学生的成绩按照分数线分为优、良、中、及格、和不及格,对应的分数线如下: 等级 优 良 中 及格 不及格 分数区间 90-100 80-89 70-79 60-69 0-59 分数在该区间的概率 10% 30% 40% 10% 10% 现在... -
NC数学考试JAVA实现
2020-05-22 13:20:16题目 分析 通过前缀和来求取区间分数和,从左到又枚举区间,答案及当前区间与之前最大...因为如果之后有更优的区间选择的话,枚举到后面这个区间时会更新答案,避免重复计算。 代码 import java.util.Scanner; publi -
Matlab程序设计
2014-06-22 14:55:031.switch-case-end结构 function grade_assess(Name,Score) %此函数用来评定学生的成绩 %Name,Score为参数,需要用户输入 %Name中的元素为学生姓名 ...%将分数区间划开:优(85~100),良(70~84),及格(60~69 -
poj 1390 Blocks
2015-01-19 00:08:28黑书上的例题,类似区间dp一般是dp[i][j]表示区间状态(i,j)能取到的最优值,这题用dp[i][j][k],这个k看似与最优值没啥关系。。仔细一想却很巧妙,他假设之后会有k个与第j段颜色相同的方块一起消,这样在后面某段... -
uva 10559——Blocks
2015-12-18 20:04:47题意:有n个带颜色的方块,同种颜色的方块连成一个区域,每次可以消除一个区域的方块x,然后得到分数x2,右边的方块左移,然后问求最大的分数。 思路:区间dp,dp(i,j,k)表示区间(i,j)在右边添上k个颜色... -
R语言Wald检验 vs 似然比检验
2019-09-04 15:25:18在这篇文章中,我将修改Wald和似然比检验的优缺点。我将重点关注置信区间而不是检验 。 示例 我们将X表示观察到的成功次数的随机变量,x表示其实现的值。似然函数只是二项式概率函数,但参数是模型参数。所以ML.... -
Blocks && Fixing the Great wall
2019-07-18 15:47:00\(dp[i][j]\) 表示处理完 \([i...j]\) 的最大分数 然后你会发现这种方法连样例1都不能搞定 因为 \(dp[i][j]\) 可能受到后面一些同色块的影响,导致直接处理不能获得最优值 那怎么办? 哪有问题就解决哪里 添加一位 \... -
洛谷 P5057 [CQOI2006]简单题(树状数组)
2019-09-25 06:06:12然后发现这道题需要支持区间更改和单点查询操作,所以首先想到的是异或意义下的差分数组,于是自己便写了一个差分数组,确实好写,但很慢(可能我写的不优),下面是五十分的异或意义下的差分的代码: 1 #... -
bzoj3316 jc loves mkk 二分&单调队列
2015-12-22 21:43:47这道题目居然还要狗血的分数输出,真是卡精度,果断long double。 首先破环成链,然后二分答案x,用每一项减去x,那么如果有L~R的区间内且和大于0的这么一段存在,记录一下区间返回1就行了。 如何判断呢?其实... -
洛谷P3957 跳房子
2018-05-15 21:19:51发现答案的可行区间是单调的,所以二分答案,容易推出f[i]表示到达第i个格子的最大值,枚举上一步跳了多少来转移 然后仔细观察可以发现对于一个状态,如果有比他后面的状态比他答案大的话,显然不会优..于是可以.... -
BZOJ 4476送礼物
2018-11-05 21:17:03题目大意:一个整数序列n,给定一个长度范围...首先这个答案肯定是单调的,我们可以二分答案,把求最优值的问题转化为判定性问题。那么我们只差一个check函数。我们二分一个mid,如果不考虑区间长度在L到R之内的话,... -
可以私聊QQ1457785526
2020-12-15 20:57:22你只需要在原数组中根据优秀与合格的分数线,按德、才双优,德优,德胜才,合格的,其它的顺序(同一种情况按总分从高到低排列)进行就地分类重排,输入由测试程序... -
文本挖掘tmSVM开源项目包含Python和Java两种版本带参考文档
2014-02-23 12:09:02包括Libsvm、Liblinear包的选择,分词,词典生成,特征选择,SVM参数的选优,SVM模型的训练等都可以一步完成。 利用生成的模型对未知文本做预测。并返回预测的标签以及该类的隶属度分数。可自动识别libsvm和... -
想知道北邮各个组过院线的人数、分数分布?(请查阅 2. 初试成绩排名) 想知道北邮各学院各组的复试名单、每个组的原报与调剂情况?(请查阅3. 复试名单) 想知道北邮各学院各组的差额复试比、录取情况、复试刷人...
-
numpy基本操作
-
在Windows上编译FreeRDP
-
【布道者】Linux极速入门
-
项目管理工具与方法
-
基于Qt的LibVLC开发教程
-
西南科技大学《电路分析》试题库(有答案).pdf
-
java如何构建多模块项目实现工具类,公共类的分模块
-
Mysql数据库面试直通车
-
西京学院《多媒体技术及应用》期末考试试卷.pdf
-
浙江科技学院《土木工程施工》07-12历年期末考试试卷(含答案).pdf
-
Vue——解决退出登陆后返回上一页问题
-
zxf QT学习
-
项目经理成长之路
-
西南科技大学《概率论与数理统计》公式整理(超全版).pdf
-
浙江科技大学《材料力学》期末复习题.pdf
-
中国计量学院《工程图学》历年期末考试试卷(含答案).pdf
-
2021_拥抱零信任安全模型_英中对照.pdf
-
MySQL NDB Cluster 负载均衡和高可用集群
-
分库分表后如何解决不同维度查询的问题
-
华为1+X——网络系统建设与运维(中级)