T1:绑腿跑
题目描述
HZOI 有 N 个小盆友，每天他们都会按同样的站位顺序进行各项体育活动。
一天，HZOI的首领决定组织一个“绑腿跑”的比赛。为了安全起见，首领会从他们当前的队列中选出一个连续的区间来进行这个比赛。
但是，众所周知，如果参加比赛的小盆友要玩得开心，而且安全的话，那么参加比赛的小盆友们的身高差距不能太大。
（你可以想想，你和姚明站在一起绑腿跑，啧啧啧……后果不堪设想……）
HZOI 的首领安排了 Q 个小组，已知每个小盆友的身高。
对每个小组，求出他们当中最高和最低的小盆友的身高差是多少。
输入格式
第 1 行: 两个空格隔开的整数，N 和 Q。
第 2..N+1 行: 第 i+1 行包含一个整数表示第 i 个小盆友的身高。
第 N+2..N+Q+1 行: 每行包含两个整数 A 和 B，表示该小组的范围是从 A 到 B。
输出格式
第 1..Q 行: 每行包含一个整数来表示该小组的最大身高差。
样例
样例输入
6 3
1
7
3
4
2
5
1 5
4 6
2 2
样例输出
6
3
0
数据范围与提示
1 ≤ N ≤ 50,000
1 ≤ Q ≤ 200,000
1 ≤ 身高 ≤ 1,000,000
1 ≤ A ≤ B ≤ N思路：这道题就是一个裸的线段树，建树后进行区间查询最大值和最小值就可以了
代码：
#include <bits/stdc++.h>
#define lson (gjd<<1)
#define rson (gjd<<1|1)
#define N 1000010
using namespace std;
int n,q,l,r,ans,a[N],ans1,ans2;
long long maxx=0,minn=0x3fff;//最大值初始化成极小值，最小值初始化成极大值
struct stu{
int l,r,max,sum,min;
}tree[N<<2];
void build(int gjd,int l,int r){
tree[gjd].l=l;
tree[gjd].r=r;
if(l==r){
tree[gjd].min=tree[gjd].max=a[l];
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
tree[gjd].max=max(tree[lson].max,tree[rson].max);
tree[gjd].min=min(tree[lson].min,tree[rson].min);
}
int queryx(int gjd,int l,int r){//查询最大值
if(l<=tree[gjd].l&&tree[gjd].r<=r)
return tree[gjd].max;
int mid=(tree[gjd].l+tree[gjd].r)>>1;
int ans=0;//求大赋小
if(l<=mid) ans=max(ans,queryx(lson,l,r));
if(r>mid) ans=max(ans,queryx(rson,l,r));
return ans;
}
int queryn(int gjd,int l,int r){//查询最小值
if(l<=tree[gjd].l&&tree[gjd].r<=r)
return tree[gjd].min;
int mid=(tree[gjd].l+tree[gjd].r)>>1;
int ans=0x3f3f3f3f;//求小赋大
if(l<=mid) ans=min(ans,queryn(lson,l,r));
if(r>mid) ans=min(ans,queryn(rson,l,r));
return ans;
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=1;i<=q;i++){
cin>>l>>r;
cout<<queryx(1,l,r)-queryn(1,l,r)<<endl;
}
return 0;
}T2：可怜与超市
设dp[i][j][0/1]表示当前考虑到第i个物品（以i为根的子树中），买了j个物品的代价，0表示不用i的优惠券，1表示使用
初始状态：dp[i][1][1]=c[i]-d[i],dp[i][1][0]=c[i],dp[i][0][0]=0，其他都是最大值
目标：ans=max(i),(dp[1][i][1]<=b)
转移： dp[x][j+k][1]=min(dp[x][j][1]+min(dp[y][k][0],dp[y][k][1]))
dp[x][j+k][0]=min(dp[x][j][0]+dp[y][k][0])
x表示当前节点，y表示当前搜索到的x的儿子，j是枚举的当前x的size，k是枚举的y的size
方程的话，你看看它代表什么就能理解了
有人说要特判k=0时的情况，因为如果你用优惠券，就必须买这个产品，所以没有dp[i][0][1]这种情况
但其实初始状态中我们把它设成了最大值，所以不会对结果有影响
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5005
#define ll long long
using namespace std;
ll n,b,c[N],d[N],x[N],ans=0;
ll to[N<<1],nxt[N<<1],head[N],cnt=0;
void add(ll x,ll y){
cnt++;
to[cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int size[N],dp[N][N][2];
void dfs(ll rt){
size[rt]=1;
dp[rt][1][1]=c[rt]-d[rt],dp[rt][1][0]=c[rt],dp[rt][0][0]=0;
for(ll i=head[rt];i;i=nxt[i]){
ll y=to[i];
dfs(y);
for(ll j=size[rt];j>=0;j--){
for(ll k=size[y];k>=0;k--){
dp[rt][j+k][1]=min(dp[rt][j+k][1],dp[rt][j][1]+min(dp[y][k][0],dp[y][k][1]));
dp[rt][j+k][0]=min(dp[rt][j+k][0],dp[rt][j][0]+dp[y][k][0]);
}
}
size[rt]+=size[y];
}
}
int main(){
memset(dp,0x3f,sizeof(dp));
scanf("%lld%lld",&n,&b);
scanf("%lld%lld",&c[1],&d[1]);
for(ll i=2;i<=n;i++){
scanf("%lld%lld%lld",&c[i],&d[i],&x[i]);
add(x[i],i);
}
dfs(1);
for(ll i=1;i<=n;i++){
if(dp[1][i][1]<=b)
ans=i;
}
printf("%lld\n",ans);
return 0;
}T2转载于:https://www.cnblogs.com/Juve/p/11203774.html 学长提供思路，感谢
T3：序列块
题目描述
给你一个长度为n的序列a。
如果一个序列的构成满足以下条件，我们称之为“大漂亮”：
1.该序列是由若干个序列块组成
2.每个序列块的开头表示该序列块的长度 ，后面 个数为该序列块的元素。
例如[3,3,4,5,2,6,1]和[1,8,4,5,2,6,1]都是“大漂亮”。但是[1],[1,4,3],[3,2,1]不是。
每一次操作，你可以从序列中删除任意一个元素。
求使原序列变成“大漂亮”的最小的操作次数。
输入格式
第一行一个整数t，表示测试数据组数。
对于每组测试数据：
第一行一个整数n，表示序列的长度
第二行n个整数，表示序列的每个元素ai。
输出格式
每组数据输出一行，包含一个整数，表示最小的操作次数。
样例
样例输入
7
7
3 3 4 5 2 6 1
4
5 6 3 2
6
3 4 1 6 7 7
3
1 4 3
5
1 2 3 4 5
5
1 2 3 1 2
5
4 5 5 1 5
样例输出
0
4
1
1
2
1
0
数据范围与提示
1<=t<=10
1<=n<=2*10^5
1<=ai<=10^6
数据有梯度
思路：定义dp[i]表示让序列从i到n变成大漂亮的最小操作次数，则有两种方法可以满足条件：
1.删除第i个数，答案等于让i+1到n变成大漂亮的次数加1，即dp[i]=dp[i+1]+1
2.以ai开关作为一个序列块，让后面的序列块变成大漂亮即可，则dp[i]=dp[i+a[i]+1]
最后再将两个式子求最小值即可
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int t,n,ans,a[N],f[N];
int main(){
cin>>t;
while(t--){
memset(f,0x3f,sizeof(f));
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[n+1]=0;
for(int i=n;i>=1;i--) f[i]=min(f[i+1]+1,f[i+a[i]+1]);
printf("%d\n",f[1]);
}
return 0;
}
T4：送礼物
博主是蒟蒻还没做出来~
敬请期待更新~
#一名爱打篮球的oier#
标签：rt,min,int,测试,ans,序列,2.23,dp From： https://www.cnblogs.com/hzoiwzs/p/18030261