3
18
2016
1

Diary of March 18th

刷BZOJ ing...
上午听了AK爷和Dirak两位神犇的讲课
感觉自己太弱了去做了一下树形DP和数位DP
UPD Mar.20th 0:25 我已经傻了……BZOJ1492终于A掉了 感动


树形DP
$f_{i,j,k}$ 表示第 $i$ 类装备有 $j$ 个用于上层的合成,
并且在它和它的子树一共用了 $k$ 元钱的最大力量。
还要用到一个临时数组 $g_{i,j}$,
表示到这个装备的第 $i$ 棵子树为止,一共用了 $j$ 元钱的最大力量
先 $O(N)$ 扫一遍处理出合成上限 $Mxb_i$ 和总单价 $Cst_i$
DP时先把子树都处理出来
然后枚举这个装备合成或者买多少个,更新答案
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=55,M=2005;
char ch[10];
int n,m,cnt,val[N],to[N],next[N],head[N];
void AddEdge(int u,int v,int w){
	to[cnt]=v;next[cnt]=head[u];val[cnt]=w;head[u]=cnt++;
}
int idx[N],Cst[N],Mxb[N],in[N],Rt,Pow[N],g[N][M],f[N][105][M];
void DFS(int u){
	int Limit=m;
	Cross(i,u){
		int v=to[i];DFS(v);
		Cst[u]+=val[i]*Cst[v];
		Limit=min(Limit,Mxb[v]/val[i]);
	}
	Limit=min(Limit,m/Cst[u]);
	Mxb[u]=min(Limit,Mxb[u]);
}
void DP(int u){
	int Tot=0; 
	Cross(i,u) DP(to[i]),idx[to[i]]=++Tot;
	Rep(l,0,Mxb[u]){
		memset(g[0],0,(m+5)*4);
		Rep(i,1,Tot) memset(g[i],224,(m+5)*4);
		Cross(i,u){
			int v=to[i],nx=idx[to[i]];
			Rep(j,Cst[v]*val[i]*l,m) Drp(k,m,j)
				g[nx][k]=max(g[nx][k],g[nx-1][k-j]+f[v][val[i]*l][j]);
		}
		Rep(j,0,l) Rep(k,l*Cst[u],m)
			f[u][j][k]=max(f[u][j][k],g[Tot][k]+Pow[u]*(l-j));
	}
}
int main(){
	n=IN(),m=IN();
	cnt=0,memset(head,-1,sizeof head);
	Rep(i,1,n){
		Pow[i]=IN();
		scanf("%s",ch);
		if (ch[0]=='A'){
			int lt=IN();
			Cst[i]=0,Mxb[i]=m;
			Rep(j,1,lt){
				int v=IN(),w=IN();
				AddEdge(i,v,w);
				in[v]++;
			}
		}
		else{Cst[i]=IN();Mxb[i]=IN();}
	}
	Rep(i,1,n) if (!in[i]){Rt=i;break;}
	DFS(Rt);
	memset(f,224,sizeof f);
	DP(Rt);
	OUT(f[Rt][0][m]);
}
数位DP
先处理 $1\sim R-1$ 的答案,再减去 $1\sim L-1$ 的答案。
假设我们现在在处理 $L-1$
$f_{i,j,k}$ 表示做了 $i$ 位,积是 $j$,
$k$ 表示是否已经比 $L-1$ 要小,这种状态的数有多少。
然而积太大了存不下,于是就可以先把$\le n$且质因数只有2,3,5,7的BFS出来
这样只有5000+个
然后就可以愉悦地DP了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
int a[5200],h,t,n,to[5200][10];
ll L,R;
map<int,int>mp;
void Init(){
	h=1,t=0;
	a[++t]=1,mp[1]=1;
	while (h<=t){
		int nx=a[h],sx=min(9,n/nx);
		to[h][1]=h;
		Rep(j,2,sx){
			int fac=nx*j;
			if (!mp[fac]) mp[fac]=++t,a[t]=fac;
			to[h][j]=mp[fac]; 
		}
		h++;
	}
}
int dig,b[20];
void GetDig(ll a){
	dig=0;
	for (;a;b[++dig]=a%10,a/=10);
	Rep(i,1,dig/2) swap(b[i],b[dig-i+1]);
}
ll f[20][5200][2];
ll Solve(ll n){
	if (!n) return 0;
	GetDig(n);
	memset(f,0,sizeof f);
	f[0][1][1]=1;
	Rep(i,0,dig-2) Rep(j,1,t) if (f[i][j][1])
		Rep(k,1,9) if (to[j][k]) f[i+1][to[j][k]][1]+=f[i][j][1];
	ll ret=0;
	Rep(i,1,dig-1) Rep(j,1,t) ret+=f[i][j][1];
	memset(f,0,sizeof f);
	f[0][1][0]=1;
	bool zro=0;
	Rep(i,0,dig-1){
		if (!b[i+1]) zro=1;
		Rep(j,1,t){
			if (f[i][j][0]&&!zro){
				if (to[j][b[i+1]]) f[i+1][to[j][b[i+1]]][0]+=f[i][j][0];
				Rep(k,1,b[i+1]-1) if (to[j][k]) f[i+1][to[j][k]][1]+=f[i][j][0];
			}
			if (f[i][j][1]){
				Rep(k,1,9) if (to[j][k]) f[i+1][to[j][k]][1]+=f[i][j][1];
			}
		}
	}
	Rep(j,1,t) ret+=f[dig][j][1];
	if (!zro) Rep(j,1,t) ret+=f[dig][j][0];
	return ret;
}
int main(){
	n=IN(),L=IN(),R=IN();
	L--,R--;
	Init();
	OUT(Solve(R)-Solve(L));
}
听说昨天第三题能用CDQ分治……于是想学一学
就拿这题练手
然而感觉还是不会 所以就边写题解边码代码辣
首先我想了想   $N^2$ DP是长这样的:
$f_i$表示在第 $i$ 天把所有票都卖掉然后所有钱都用来买票最多能有几张A票
$f_i=\frac{rate_i*max\{f_j*a_i+\frac{f_j}{rate_j}*b_i\}}{a_i*rate_i+b_i}$
考虑两个决策 $j$ 和 $k$
$j$ 比 $k$ 优当且仅当
$f_j*a_i+\frac{f_j}{rate_j}*b_i>f_k*a_i+\frac{f_k}{rate_k}*b_i$
$☞ (f_j-f_k)*a_i>(\frac{f_k}{rate_k}-\frac{f_j}{rate_j})*b_i$
设 $g_i=\frac{f_i}{rate_i}$,那么就是
$\frac{g_k-g_j}{f_k-f_j}<-\frac{a_i}{b_i}$
然后……然后我就不知道了
哦我造了!!为了容易搞,
把 $mid+1\sim r$ 按斜率排序,把 $l\sim mid$ 按 $X$ 坐标排序……
就可以两个指针乱搞了
我擦 就这么没了?感觉有点水啊
UPD Mar.20th 0:26 我收回上面的话
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
#define eps 1e-13
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=100005;
struct Day{
	double a,b,rate,k,f;
	int id;
}a[N],b[N];
double s,Ans;
bool cmp(const Day&a,const Day&b){return a.k>b.k;}
double K(int j,int k){
	if (fabs(a[j].f-a[k].f)<eps) return a[j].f/a[j].rate>a[k].f/a[k].rate?1e20:-1e20;
	return (a[j].f/a[j].rate-a[k].f/a[k].rate)/(a[j].f-a[k].f);
}
int Top,S[N],n;
void Solve(int l,int r){
	if (l==r){
		a[l].f=max(a[l].f,Ans/(a[l].a+a[l].b/a[l].rate));
		Ans=max(Ans,a[l].f*(a[l].a+a[l].b/a[l].rate));
		return;
	}
	int mid=l+r>>1,z1=l,z2=mid+1;
	Rep(i,l,r){
		if (a[i].id<=mid) b[z1++]=a[i];
			else b[z2++]=a[i];
	}
	Rep(i,l,r) a[i]=b[i];
	Solve(l,mid);
	Top=0;
	Rep(i,l,mid){
		while (Top>1&&K(i,S[Top])+eps>K(S[Top],S[Top-1])) Top--;
		S[++Top]=i;
	}
	int now=1;
	Rep(i,mid+1,r){
		while (now<Top&&K(S[now+1],S[now])+eps>a[i].k) now++;
		a[i].f=max(a[i].f,a[S[now]].f*(a[i].a+a[i].b/a[S[now]].rate)/(a[i].a+a[i].b/a[i].rate));
	}
	Solve(mid+1,r);
	z1=l,z2=mid+1;
	Rep(i,l,r){
		if (z2>r||(z1<=mid&&a[z1].f<a[z2].f)) b[i]=a[z1++];
			else b[i]=a[z2++];
	}
	Rep(i,l,r) a[i]=b[i];
}
int main(){
	n=IN(),s=IN();
	Rep(i,1,n) scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].rate),a[i].k=-a[i].a/a[i].b,a[i].id=i;
	sort(a+1,a+n+1,cmp);
	Ans=s;
	Solve(1,n);
	printf("%.3lf\n",Ans);
}

 

Category: Diary | Tags: DP 树形DP 数位DP 凸包 | Read Count: 660
celeb networth 说:
Jun 07, 2023 06:52:10 PM

I learned a lot from the insight you shared here. It's good to learn more about this topic, and if you have some free time or you're curious about some celebrity basic information, you can visit celeb networth post and search for it.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com