关键词：
本题和某一年的oi题非常相似，都是经典套路
我们知道我们在送完食物后既可以向前送也可以回头送，这就体现了区间dp的思想
为什么我们这次的区间dp不用枚举第三维k来枚举从哪里送过来呢？
因为送货员不是傻子，他如果送到你这了，那么在你们两之间的可以都顺路送了，所以我们只需要枚举两个位置就行
这题的输入不一定递增，所以建议输入完后排序
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+10; const int inf=0x3f3f3f3f; ll f[1100][1100][2]; ll s[N]; struct node int x; int v; bool operator <(const node & t) return x<t.x; num[N]; int main() int i; int n; int v; int x; while(cin>>n>>v>>x) int cnt=0; for(i=1;i<=n;i++) cin>>num[i].x>>num[i].v; n++; num[n].x=x; num[n].v=0; sort(num+1,num+1+n); int i; int pos; for(i=1;i<=n;i++) s[i]=s[i-1]+num[i].v; for(i=1;i<=n;i++) if(num[i].x==x) pos=i; break; memset(f,0x3f,sizeof f); int len,j,k; int l,r; f[pos][pos][1]=f[pos][pos][0]=0; for(len=2;len<=n;len++) for(l=1;l+len-1<=n;l++) r=l+len-1; f[l][r][1]=min(f[l+1][r][0]+(s[l]+s[n]-s[r])*(num[r].x-num[l].x),f[l+1][r][1]+(s[l]+s[n]-s[r])*(num[l+1].x-num[l].x)); f[l][r][0]=min(f[l][r-1][0]+(s[l-1]+s[n]-s[r-1])*(num[r].x-num[r-1].x),f[l][r-1][1]+(num[r].x-num[l].x)*(s[l-1]+s[n]-s[r-1])); cout<<min(f[1][n][1],f[1][n][0])*v<<endl;
zoj-3469——fooddelivery
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3469dp[i][j][0]:=派送区间[i,j]的用户并且最后派送i时的最小值dp[i][j][1]:=派送区间[i,j]的用户并且最后派送j时的最小值dp[i][j][0]=min(dp[i+1][j][0]+cost1,dp[i+1][j][1]+cost2)dp 查看详情
zoj3469fooddelivery
zoj3469FoodDelivery题面一维数轴上有一个外卖配送员和(1000)个客户，每个客户(i)的怒气值是他收到外卖的时间乘(b[i])（(b[i])由题目给定），给出配送员速度，求一个方案使得所有客户的怒气值之和最小，输出最小怒气值之和。题解... 查看详情
zoj3469fooddelivery（经典区间dp）(代码片段)
本题和某一年的oi题非常相似，都是经典套路我们知道我们在送完食物后既可以向前送也可以回头送，这就体现了区间dp的思想为什么我们这次的区间dp不用枚举第三维k来枚举从哪里送过来呢？因为送货员不是傻子，他如果送到... 查看详情
fooddeliveryzoj-3469（区间dp）
FoodDelivery ZOJ-3469 题意：快递员送外卖，n个客户，起始位置为x，速度为v，每个客户单位时间不满意度增加hi，问最少增加多少不满意度。每一个客户可能是从左侧送到或者从右侧送到。1#include<bits/stdc++.h>2usingnamespacest... 查看详情
zoj3469区间dp
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4255这特喵的不就是河南省某届省赛那道开关灯的强化版题目吗。。。。一是数据增强了可能爆int，所以用的LL才A，还有就是给出的坐标不一定有序注意排序，还有起点不一定是送餐点... 查看详情
最小割经典题（两个点依附在一起的情况）poj3469
DualCoreCPUTimeLimit:15000MS MemoryLimit:131072KTotalSubmissions:25099 Accepted:10866CaseTimeLimit:5000MSDescriptionAsmoreandmorecomputersareequippedwithdualcoreCPU,SetagLilb,theChiefTechnol 查看详情
zoj-4089-littlesubandisomorphismsequences(代码片段)
...字串长度，它在其他位置存在同构。当存在两个不相交的区间同构时，如：1、2、……、n-1、n、n+1、……、m、m+1、m+2、……、m+n-1、m+n;(假设m>n&&[1,n]和[m+1,m+n]同构)那么K=n显然是存在的。但是这不是... 查看详情
zoj-1610countthecolors线段树区间修改
Paintingsomecoloredsegmentsonaline,somepreviouslypaintedsegmentsmaybecoveredbysomethesubsequentones.Yourtaskiscountingthesegmentsofdifferentcolorsyoucanseeatlast.InputThefirstlineofeachdatasetcontains 查看详情
《入门经典》——6.28
贪心策略：选择不相交区间问题。 抽象化描述：给出n个区间[ai,bi]，从中选出尽可能多的区间，使得这些区间能够不相交。实际问题当中的应用：这个模型常常以日程安排的实际问题作为载体进行考察。 贪心策略分析：&... 查看详情
zoj1610countthecolors区间覆盖求染色段
CounttheColorsTimeLimit:2Seconds MemoryLimit:65536KBPaintingsomecoloredsegmentsonaline,somepreviouslypaintedsegmentsmaybecoveredbysomethesubsequentones.Yourtaskiscountingthesegm 查看详情
zoj-1610countthecolors（线段树区间更新）(代码片段)
...题意给一个n，代表n次操作，接下来每次操作表示把[l，r]区间的线段涂成k的颜色其中,l,r,k的范围都是0到8000。分析把区间看作点，即[3,4]看作点4。查询时进行前序遍历，记录上一段的颜色，不连续的就+1。注意区间的范围可达8000... 查看详情
zoj3299(区间改动+离散化)
...n个由小木块组成的长条木块要掉下来。给出木块的左右区间，然后有给了m个木板的左右区间和高度用来接住木块，由于木块是由小木块接触组成的，也就是木板能够接住一部分的木块。剩下的会继续掉落，问最后每一个木板上... 查看详情
zoj2599：graduatedlexicographicalordering(很经典的数位dp)
Considerintegernumbersfrom1ton.Letuscallthesumofdigitsofanintegernumberitsweight.Denotetheweightofthenumberxasw(x).Nowletusorderthenumbersusingsocalled graduatedlexicographicalordering,orshorterg 查看详情
zoj1610countthecolors(区间染色)
...，如果所占区段为0则不用输出。解题思路：基本还是跟区间染色问题差不多，但要注意一些东西①这里l,r指的是端点。比如3141122343这组数据最后输出结果为:112131原因是 查看详情
zoj3953zju2017校赛（贪心）
题意：给出n个区间，求至少删掉多少个区间使得不存在区间a,b,c两两相交 (定义两个区间相交是，区间[l1,r1]和区间[l2,r2]相交，当且仅当存在一个数x，l1<=x<=r1且l2<=x<=r2) 输入第一行为T,表示测试数据组数 ... 查看详情
zoj-3537cake(凸包+区间dp+最优三角剖分)
DescriptionYouwanttoholdaparty.Here‘sapolygon-shapedcakeonthetable.You‘dliketocutthecakeintoseveraltriangle-shapedpartsfortheinvitedcomers.Youhaveaknifetocut.Thetraceofeachcutisalinesegment,whosetwoen 查看详情
zoj2112dynamicrankings（带修改的区间第k大，分块+二分搜索+二分答案）
DynamicRankingsTimeLimit: 10Seconds MemoryLimit: 32768KBTheCompanyDynamicRankingshasdevelopedanewkindofcomputerthatisnolongersatisfiedwiththequeryliketosimplyfin 查看详情
zoj3537cake（凸包+区间dp）(代码片段)
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3537题目大意：给出一些点表示多边形顶点的位置，如果不是凸多边形（凸包）则不能切，直接输出"Ican‘tcut."切多边形时每次只能在顶点和顶点间切，每切一次的花费为co... 查看详情