• This is a lite version of the full Water+ plugin. It has most of Water+ functionality, without the additional water map generation tools. Water+ lite shader has reflections, refractions, fast ...
• Description n天，每天都要吃西瓜，第i天可以花p[i]的代价买一个可以吃第d[i]天的大西瓜，如果某天买了新的西瓜就会把没吃完的西瓜都扔掉吃新的西瓜，问n天都吃西瓜的最小代价 Input 多组用例，每组用例首先输入...
Description  n天，每天都要吃西瓜，第i天可以花p[i]的代价买一个可以吃第d[i]天的大西瓜，如果某天买了新的西瓜就会把没吃完的西瓜都扔掉吃新的西瓜，问n天都吃西瓜的最小代价  Input  多组用例，每组用例首先输入一整数n表示要吃西瓜的天数，之后n个整数p[i]表示第i天西瓜的价格，最后n个整数d[i]表示第i天西瓜可以吃的天数（用例数不超过200,1<=n<=5e4,1<=p[i],d[i]<=1e5）  Output  输出n天都吃西瓜的最小代价  Sample Input  4  10 20 1 40  3 2 3 1  Sample Output  11  Solution  从i点向min(i+d[i],n+1)连一条边权为p[i]的边表示买了这个西瓜就可以维持[ i,min(i+d[i],n+1) )这个区间的需求，从i+1向i连边权为0的边表示一个西瓜不需要吃完就可以扔掉买新的西瓜，最后才从1到n+1的最短路即为维持[1,n+1)这个区间需求的最小代价  Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 1e12
#define maxn 555555
struct edge
{
int to,next,cost;
}g[2*maxn];
ll dis[maxn];//所有点到起点的最短距离
void init()//初始化
{
tol=0;
}
{
g[tol].cost=c;
g[tol].to=v;
}
void spfa(int s)//单源最短路,s是起点
{
bool vis[maxn];
memset(vis,0,sizeof(vis));
queue<int>que;
for(int i=0;i<maxn;i++)dis[i]=INF;
dis[s]=0,vis[s]=1;
que.push(s);
while(!que.empty())
{
int u=que.front();que.pop();
vis[u]=0;
{
int v=g[i].to,c=g[i].cost;
if(dis[v]>dis[u]+c)
{
dis[v]=dis[u]+c;
if(!vis[v])vis[v]=1,que.push(v);
}
}
}
}
int n,p[maxn],d[maxn];
int main()
{
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)scanf("%d",&p[i]);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
init();
spfa(1);
printf("%lld\n",dis[n+1]);
}
return 0;
}
展开全文
• Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope that they can have watermelon to eat every day during the summer vacation....
• Watermelon Full of Water Time Limit: 3 Seconds Memory Limit: 65536 KB Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope


Watermelon Full of Water

Time Limit: 3 Seconds
Memory Limit: 65536 KB

Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope that they can have watermelon to eat every day during the summer vacation. Suppose there are n days and every day they can buy only one watermelon. The price of watermelon may be different in each day. Besides, sometimes the watermelon they choose to buy may be very big, which means if they buy this watermelon, they will need several days to eat it up. The students want to spend the minimum money to buy enough watermelon so that they can eat watermelon every day. Can you help them?
Notice: When they buy a new watermelon, if they still have an old watermelon, they will throw the old one into dustbin. For example, suppose they buy a watermelon on the fisrt day, and it needs 4 days to eat up the watermelon. But if they buy a new watermelon on the second day and it needs 2 days to eat up the new watermelon, then they will throw the old one, and they have to buy a new watermelon on the fourth day since they don't have any watermelon to eat on that day.
Input
The input contains multiple test cases ( no more than 200 test cases ). In each test case, first there is an integer, n ( 1 <= n <=50000 ) , which is the number of summer days. Then there is a line containing n positive integers with the ith integer indicating the price of the watermelon on the ith day. Finally there is line containing n positive integers with the ith integer indicating the number of days students need to eat up the watermelon bought on the ith day. All these integers are no more than 100000 and integers are seperated by a space.
Output
For each case, output one line with an integer which is the minimum money they must spend so that they can have watermelon to eat every day.
Sample Input
4
10 20 1 40
3 2 3 1

Sample Output
11

题意：每天可以买一个西瓜，每个西瓜有相应的价钱，和可以吃多少天，要求每天都吃西瓜，问你最少的花费是多少。
思路：首先逆推，第k天的最小花费是num1[k]+dp[k+  (1...num2[k])  ]，然后因为数据量比较大，需要用线段树来得到后面部分的最小值是多少。
AC代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
long long dp[50010],num1[50010],num2[50010];
int t=0,f[50010];
struct node
{ long long l,r,minn;
int pos;
}tree[200010];
void build(int num,int x,int y)
{ tree[num].l=x;
tree[num].r=y;
if(x==y)
{ tree[num].minn=100000*100000;
tree[num].pos=++t;
f[x]=num;
return;
}
int mid=(tree[num].l+tree[num].r)/2;
int left=2*num;
int right=left+1;
build(left,x,mid);
build(right,mid+1,y);
if(tree[left].minn<tree[right].minn)
{ tree[num].minn=tree[left].minn;
tree[num].pos=tree[left].pos;
}
else
{ tree[num].minn=tree[right].minn;
tree[num].pos=tree[right].pos;
}
}
void update(int num,int x)
{ tree[num].minn=x;
num/=2;
int left,right;
while(num>0)
{ left=2*num;right=left+1;
if(tree[left].minn<tree[right].minn)
{ tree[num].minn=tree[left].minn;
tree[num].pos=tree[left].pos;
}
else
{ tree[num].minn=tree[right].minn;
tree[num].pos=tree[right].pos;
}
num/=2;
}
}
int query(int num,int x,int y)
{ if(tree[num].l==x && tree[num].r==y)
return tree[num].pos;
int mid=(tree[num].l+tree[num].r)/2;
int left=2*num;
int right=left+1;
if(y<=mid)
return query(left,x,y);
else if(x>mid)
return query(right,x,y);
else
{ int pos1,pos2;
pos1=query(left,x,mid);
pos2=query(right,mid+1,y);
if(dp[pos1]<dp[pos2])
return pos1;
else
return pos2;
}
}
int main()
{ int n,i,j,k;
while(~scanf("%d",&n))
{ t=0;
for(i=1;i<=n;i++)
scanf("%d",&num1[i]);
for(i=1;i<=n;i++)
scanf("%d",&num2[i]);
dp[n]=num1[n];
build(1,1,n+1);
for(i=n-1;i>=1;i--)
{ if(i+num2[i]>=n+1)
dp[i]=num1[i];
else
dp[i]=min(dp[i+1]+num1[i],dp[query(1,i+1,i+num2[i])]+num1[i]);
update(f[i],dp[i]);
}
printf("%lld\n",dp[1]);
}
}



展开全文
• Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope that they can have watermelon to eat every day during the summer vacation....
Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope that they can have watermelon to eat every day during the summer vacation. Suppose there are n days and every day they can buy only one watermelon. The price of watermelon may be different in each day. Besides, sometimes the watermelon they choose to buy may be very big, which means if they buy this watermelon, they will need several days to eat it up. The students want to spend the minimum money to buy enough watermelon so that they can eat watermelon every day. Can you help them?
Notice: When they buy a new watermelon, if they still have an old watermelon, they will throw the old one into dustbin. For example, suppose they buy a watermelon on the fisrt day, and it needs 4 days to eat up the watermelon. But if they buy a new watermelon on the second day and it needs 2 days to eat up the new watermelon, then they will throw the old one, and they have to buy a new watermelon on the fourth day since they don’t have any watermelon to eat on that day.
Input The input contains multiple test cases ( no more than 200 test cases ). In each test case, first there is an integer, n ( 1 <= n <=50000 ) , which is the number of summer days. Then there is a line containing n positive integers with the ith integer indicating the price of the watermelon on the ith day. Finally there is line containing n positive integers with the ith integer indicating the number of days students need to eat up the watermelon bought on the ith day. All these integers are no more than 100000 and integers are seperated by a space.
Output For each case, output one line with an integer which is the minimum money they must spend so that they can have watermelon to eat every day.
Sample Input 4 10 20 1 40 3 2 3 1 Sample Output 11
动态规划： dp[i]代表i天内每天都有西瓜吃的最小消费； 那么对于每天，假设选上当天的西瓜，那么dp[i - 1] + price[i]这个值在[i,i + day[i] - 1]这段时间区间内，这个值是可以用的（可以成为dp值，选最小的即可），所以这就需要维护一个区间最小值了，可以用线段树，也可以用优先队列，我用的是优先队列优化的。 线段树的话，区间更新即可，dp[i]就是线段树i点的值 注意：该题会爆long long，所以结构体内需要用LL
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 50005;

int price[N];
int day[N];
LL dp[N];
int n;
typedef struct Node{
LL x,y;
friend bool operator < (const Node &p,const Node &q){
if(p.x == q.x){
return p.y > q.y;
}else{
return p.x > q.x;
}
}
}Node;
priority_queue<Node>que;

int main()
{
while(~scanf("%d",&n)){
memset(dp,0,sizeof(dp));
for(int i = 1;i <= n;++i){
scanf("%d",&price[i]);
}
for(int i = 1;i <= n;++i){
scanf("%d",&day[i]);
}
while(!que.empty()) que.pop();
Node node;
for(int i = 1;i <= n;++i){
//在第i天买了第i个瓜，在[i,i + day[i] - 1]范围内都可以用这个值
node.x = dp[i - 1] + price[i];
node.y = i + day[i] - 1;
while(!que.empty() && que.top().y < i) que.pop();
que.push(node);
dp[i] = que.top().x;
}
printf("%lld\n",dp[n]);
}
return 0;
}


展开全文
•   题目大意： 暑假有n（1~50000）天,第i天西瓜的价格是p[i]，可以吃d[i]天，如果在第i天买了个西瓜，那么旧的西瓜要扔掉，开始吃新西瓜。 问每天都能吃到西瓜的最小花费。...p[i]表示第i天买喜欢的花费，d[i]表
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4778

题目大意：
暑假有n（1~50000）天,第i天西瓜的价格是p[i]，可以吃d[i]天，如果在第i天买了个西瓜，那么旧的西瓜要扔掉，开始吃新西瓜。
问每天都能吃到西瓜的最小花费。

题目思路：
p[i]表示第i天买喜欢的花费，d[i]表示第i天买的西瓜能吃的天数。
dp[i],表示以i为起点，最少要花费多少钱才能使i~n每天都有西瓜吃。
状态转移很显然dp[i]= (i+d[i]>n)? p[i] : min{dp[i+1]~dp[i+d[i]]}+p[i]。
很明显在取dp[i+1]~dp[i+d[i]]的过程显然不可以从i+1 ~ i+d[i]扫一遍，这样复杂度O（n*n），会超时。
所以最直接的方法就是用线段树优化。

代码：
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define eps (1e-8)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
template <class T> T _abs(T x){return (x < 0)? -x:x;}
template <class T> T _mod(T x,T y){return (x > 0)? x%y:((x%y)+y)%y;}
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
template <class T> void getmax(T& x,T y){x=(y > x)? y:x;}
template <class T> void getmin(T& x,T y){x=(x<0 || y<x)? y:x;}
int TS,cas=1;
const int M=50000+5;
ll n,p[M],d[M],mmin[M<<2],MAX;
void build(int l,int r,int rt){
mmin[rt]=MAX;
if(l==r) return;
int mid=middle;
build(lson),build(rson);
}
void pushUp(int rt){
mmin[rt]=_min(mmin[ls],mmin[rs]);
}
void update(int l,int r,int rt,int p,ll c){
if(l==r){mmin[rt]=c;return;}
int mid=middle;
if(p<=mid) update(lson,p,c);
else update(rson,p,c);
pushUp(rt);
}
ll query(int l,int r,int rt,int L,int R){
if(L<=l && r<=R) return mmin[rt];
int mid=middle;
if(R<=mid) return query(lson,L,R);
else if(mid<L) return query(rson,L,R);
else return _min(query(lson,L,mid),query(rson,mid+1,R));
}

void run(){
int i,j;
MAX=1;
for(i=1;i<=n;i++) scanf("%lld",&p[i]),MAX+=p[i];
for(i=1;i<=n;i++) scanf("%lld",&d[i]);
ll ret,tmp;
build(1,n,1);
for(i=n;i>=1;i--){
int l=i+1,r=i+d[i];
if(r>n) ret=p[i];
else ret=query(1,n,1,i+1,i+d[i])+p[i];
update(1,n,1,i,ret);
}
printf("%lld\n",ret);
}

void preSof(){
}

int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while((~scanf("%d",&n))) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}


展开全文
• AQUAS is a powerful and full-featured water system that contains a set of 12 flat water shaders for all types of platforms, environments and games. It is is highly customizable and feature rich to ...
• LAMMPS input for water Prepare initial geometry The independently developed Packmol extension can be used to generate a box of water molecules. Open the LAMMPS input dialog Prepare simulation ...
• 线段树 题意：给定n表示n天，第一行为n天每天西瓜价格，第二行为该天买的西瓜能吃的天数 问，每天都要有西瓜吃，到n天花的钱的最小值（注意，当买了第k天的西瓜，则之前的西瓜将被丢弃，也就是说，天数的计算取决于...
• GivennumBottlesfull water bottles, you can exchangenumExchangeempty water bottles for one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Return ...
• 题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3632 题目
• n天要保证每天都有西瓜吃，每天都可以买一个西瓜，每天的西瓜有不同的价格且可以吃不同的天数，求最小花费。 dp[i]=min(dp[k]+money[i])，day[k]+k>=i；用线段树维护dp[i]; #include #include ...
• K - Watermelon Full of Water Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit Status Practice ZOJ 3632 Appoint description: Description Watermelon is very p...
• 题目地址：  http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4778   算是基础的线段树题目了。。。   囧的一逼。。... 先是 tmin数组越界，没报错，还把day数组的值给改了。...
• 暑假生活开始了，夏日炎炎，集训队想要每天都吃到西瓜。已知n天，每天商店提供一个西瓜，不同的西瓜可以供集训队吃不同的天数，也有不同的价格，问集训队想保证每天都能吃到西瓜的最小花费。 单个数100000，数组...
• 问题现象 有大量的数据要做数据清洗入库，在清洗快结束了的时候报错，如下 ... nested exception is java.sql.BatchUpdateException: The table 'task_master' is full 排查步骤 根据The table 'task_master' is f
• Watermelon Full of Water Time Limit: 3 Seconds Memory Limit: 65536 KB Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they hope
• The full execution of above code is available here. Following is the simple Java code which shows how you could use the same code to write a Java application to perform scoring based on H2O MOJO ...
• 题意：有个人每天都要吃西瓜。。。每天的西瓜的价钱不同，买了西瓜后，最多可以吃ti天，每天最多买一个西瓜，如果一天买了一个西瓜，那么之前买的就要丢掉。问n天花掉的最少多少钱能保证这个人每天都能吃到西瓜。...
• Watermelon Full of Water 时间限制(普通/Java):3000MS/9000MS 运行内存限制:65536KByte 描述 Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and...
• 题目大意： 让每天都能吃到西瓜。最少需要花多少钱。 思路分析： ...dp[pos] 就表示 要让 前i天每天都有西瓜吃，最少需要花多少钱。...然后再在每个西瓜的更新部分取最小的，就可以是这个点所能得到的最小值。...
• sparkling-water是将spark和h2o集成与一体的工具，主要思想是利用h2o进行数据挖掘，而利用进行数据处理和一部分计算，具体架构如下： 我们可以从图中看到，spark对源数据做了处理，然后交给h2o进行建模，在预测...
• unity的水面特效，同时有漂浮的物理模拟。整理过文档，打包出过安卓，移动端可用。已经用在项目中中了。附带一个船模型。unity测试版本为2017.3.1f
• Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Return ...
• 题意：有n天，每天都可以买西瓜，每个西瓜的价格是ai，每个西瓜能吃bi天。问这n天每天都有西瓜吃的最小的代价是多少？如果你在第i天买了一个西瓜，那么之前买的西瓜就要全部扔掉，才能开始吃新的西瓜。...
• 常见有三种情况都有用到... 对索列进行聚合计算时通过案例学调优之--Index FULL SCAN和Index FAST FULL SCANIndex FULL SCAN和ndex FAST FULL SCAN工作原理：Index FULL SCAN 和Index FAST FULL SCAN的适用情况：适...
• Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Return ...
• 题目描述如下 You are given two jugs with capacities x and y ... There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using thes

...