ABC314 E
大致意思是给你n个轮盘，第i个轮盘等概率的p[i]个点数，玩一次c[i]价钱，问要达到m点的最小期望花费是多少，每次可以任意选一个。
乍一看很像背包，偏了方向，所以当时没有做出来。也考虑过其它的DP，关键是0怎么处理没搞明白所以赛后看他人的代码和题解
每次可以任选一个，也就说如果某个轮盘的期望最小，那就可以一只羊薅到秃。那我们的状态表示就不应该带轮盘编号了。
设f[i]是到达i花费的期望。那么轮盘里的0是无论如何也不能让一个小于i的数增长到i的。那么大佬们的处理方式是去掉为0的，让剩下的涨价.
价格变成c*p/(p-0的个数).
然后f[i]=min(f[i],(c[j]*p[j]+f[i-s[j][k]].....)/(p-t))
查看代码
#include<iostream>
using namespace std;
typedef long long ll;
int n,m,tot;
int c[205],p[205],s[205][205];
double f[205];
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>c[i]>>p[i];
for(int j=1;j<=p[i];j++)
{
cin>>s[i][j];
}
}
f[0]=0;
for(int i=1;i<=m;i++)
{
f[i]=1e9;
for(int j=1;j<=n;j++)
{
double sz=0,t=0;
for(int k=1;k<=p[j];k++)
{
if(s[j][k])sz+=f[max(0,i-s[j][k])];
else t++;
}
f[i]=min(f[i],(c[j]*p[j]+sz)/(p[j]-t));
}
}
printf("%.6lf",f[m]);
return 0;
}CF892 D
一条线上有传送门，传送门的进入范围是[l,r],进入之后可以传送到[a,b],(l<=a<=b<=r),现在有一些点，问这些点最右能到达的是多少
前几天做树状数组的题写了写离线查询，没想到这个题就用上了。然后用小根堆来维护当前最靠前查询的点，将传送门合并下，按照b的大小和l的大小排序。然后在比赛结束前30s过了。不合并传送门会TLE5。
查看代码
#include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
typedef long long ll;
struct door
{
int l,a,b,r;
}a[200005];
struct qq
{
int id;
int x;
bool operator<(qq y)const
{
return x>y.x;
}
}v;
int ans[200005];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r>>a[i].a>>a[i].b;
sort(a+1,a+1+n,[](door x,door y)->bool{
if(x.b==y.b)
{
return x.l<y.l;
}
return x.b<y.b;
});
door tmp=a[n];//从后往前合并传送门
vector<door>b;
for(int i=n-1;i>=1;i--)
{
if(a[i].b>=tmp.l)//如果tmp的传送门的左边界比当前i处传送门的右传送点小的话就合并
{
tmp.l=min(a[i].l,tmp.l);
}
else//如果不能合并了，就加到b里
{
b.push_back(tmp);
tmp=a[i];
}
}
b.push_back(tmp);//最后一个记得加进去
sort(b.begin(),b.end(),[](door x,door y)->bool{
if(x.b==y.b)
{
return x.l<y.l;
}
return x.b<y.b;
});//给合并后的传送门排序
int q;
cin>>q;
priority_queue<qq>cc;
for(int i=1;i<=q;i++)
{
cin>>v.x;
ans[i]=v.x;
v.id=i;
cc.push(v);
}//离线查询
int poi=0;//第poi个传送门
while(cc.size())
{
qq tmp=cc.top();
cc.pop();
int x=tmp.x;
while(poi<b.size()&&b[poi].b<=x)poi++;//如果传送距离小于等于当前距离不如不传送
if(poi<b.size()&&b[poi].l<=x)
{
tmp.x=b[poi].b;
ans[tmp.id]=b[poi].b;
cc.push(tmp);
}
}
for(int i=1;i<=q;i++)
cout<<ans[i]<<' ';
cout<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}CF892 E
给两个序列a,b，定义[l,r]这一段的价值是|ar-bl|+|br-al|,问总长度为k的不相交段的最大价值是多少？
它给的是一个绝对值的和，我们可以把它拆分成四种情况
那么对于一个l，我们仅需要考虑-al-bl,al-bl,al+bl,-al-bl,这四种情况，同时对应一个r，我们需要考虑ar+br,ar-br,-ar+br,-ar-br
那么我们可以分开来看。
f[l][j]表示长度为l时，第j种情况的最大值
g[l]表示长度为l时的最大值
那么我们可以每次分别将当前点作为左节点或者右节点加入看看最大值
把一个区间分成单点分两次DP的
查看代码
//#pragma GCC optimize(2)
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
//+ar-bl+br-al
//+ar-bl-br+al
//-ar+bl+br-al
//-ar+bl-br+al
const ll inf=1e18;
ll a[3005],b[3005],f[3005][4],g[3005],ope[4][4]={{1,-1,1,-1},{1,-1,-1,1},{-1,1,1,-1},{-1,1,-1,1}};
void solve()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<=n;i++)
{
for(int j=0;j<4;j++)
{
f[i][j]=-inf;
}
}
for(int j=1;j<=n;j++)
{
cin>>b[j];
g[j]=-inf;
}
g[0]=0;
for(int i=1;i<=n;i++)
{
for(int l=k;l>0;l--)
{
for(int j=0;j<4;j++)
{
f[l][j]=f[l-1][j];//不选i的a,b作为某个端点的时候记录四种情况下的最大值
}
}
for(int l=0;l<k;l++)
{
for(int j=0;j<4;j++)
{
f[l+1][j]=max(f[l+1][j],g[l]+a[i]*ope[j][0]+b[i]*ope[j][2]);//选择作为左端点
}
}
for(int l=0;l<=k;l++)
{
for(int j=0;j<4;j++)
g[l]=max(g[l],f[l][j]+b[i]*ope[j][1]+a[i]*ope[j][3]);//选择作为对应的右端点
}
}
cout<<g[k]<<"\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}