首先看到题目，n=300是个比较鲜明的特征，说明应该不是一些贪心或技巧类的题目，然后观察题目类型，每个时刻我们需要打捞一个宝藏，而每个宝藏在不同时刻被打捞的代价是不同的。首先思考到的这不就是安排一个顺序吗？贪心的sort以下，发现不同时刻的t的变量影响排序的优先级，但t我们又是未知的。思考DP，虽然不同时刻的代价是叠加的我们或许可以代价提前付，但这种顺序就是未知的题目好像不能用线性DP写，唯一能记录状态的就是状压DP，但300可以状压吗？显然不太行....以前写过那么多网络流的题还是没记住网络流的规模不就是500吗？具体的我们可以这样思考：我们现在要为每个宝藏安排一个时间t，每个t只能安排给一个宝藏，并且不同的宝藏在不同的时间是不同的，考虑到时间t与宝藏是唯一对应的关系，也就是说一个t只能给一个宝藏，不能同时给两个以上的宝藏...这不就是二分图的匹配吗？我们将所有的时间放在左边，所有的宝藏放在右边，每个点都想每个宝藏练一个边，带有边权，求最大带权匹配。由于是完全图，用KM的效率比用网络流的高，直接打KM就行了。
//不等,不问,不犹豫,不回头. #include<bits/stdc++.h> #define _ 0 #define ls p<<1 #define db double #define rs p<<1|1 #define P 1000000007 #define ll long long #define get(x) x=read() #define PLI pair<ll,int> #define PII pair<int,int> #define ull unsigned long long #define put(x) printf("%d ",x) #define putl(x) printf("%lld ",x) #define rep(x,y,z) for(int x=y;x<=z;++x) #define fep(x,y,z) for(int x=y;x>=z;--x) #define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y) using namespace std; const int N=310; const ll INF=1e18; int n,pre[N],px[N],py[N]; bool vx[N],vy[N]; ll cx[N],cy[N],slack[N],w[N][N]; queue<int>q; struct wy{int x,y,z,v;}a[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void agu(int v) { int t; while(v) { t=px[pre[v]]; px[pre[v]]=v; py[v]=pre[v]; v=t; } } inline void bfs(int s) { memset(vx,0,sizeof(vx)); memset(vy,0,sizeof(vy)); fill(slack+1,slack+n+1,INF); while(!q.empty()) q.pop(); q.push(s); while(1) { while(!q.empty()) { int x=q.front();q.pop(); vx[x]=1; rep(i,1,n) if(!vy[i]) { if(cx[x]+cy[i]-w[x][i]<slack[i]) { pre[i]=x; slack[i]=cx[x]+cy[i]-w[x][i]; if(slack[i]==0) { vy[i]=1; if(!py[i]) {agu(i);return;} else q.push(py[i]); } } } } ll d=INF; rep(i,1,n) if(!vy[i]) d=min(d,slack[i]); rep(i,1,n) { if(vx[i]) cx[i]-=d; if(vy[i]) cy[i]+=d; else slack[i]-=d; } rep(i,1,n) if(!vy[i]) { if(slack[i]==0) { vy[i]=1; if(!py[i]) {agu(i);return;} else q.push(py[i]); } } } } int main() { // freopen("1.in","r",stdin); get(n); rep(i,1,n) { get(a[i].x);get(a[i].y); get(a[i].z);get(a[i].v); } rep(i,1,n) //时间为i-1 { ll d=-INF; rep(j,1,n) { w[i][j]=-(a[j].x*a[j].x+a[j].y*a[j].y+((ll)(i-1)*a[j].v+a[j].z)*((ll)(i-1)*a[j].v+a[j].z)); d=max(d,w[i][j]); } cx[i]=d; } rep(i,1,n) bfs(i); ll ans=0; rep(i,1,n) ans+=-w[i][px[i]]; putl(ans); return (0^_^0); } //以吾之血,铸吾最后的亡魂.
简化题意：给你一个序列，同时给定m个询问，每个询问给定一个k，问序列中有多少个区间使得区间的最大值减最小值>k。O(nm)的做法可过。
询问区间的个数，套路无外乎几个，1.固定左端点，寻找符合右端点的个数；2.固定右端点，寻找左端点的个数；3.尺取法。
由于尺取法是O(n)的，我们优先考虑尺取法，固定左端点后，我们可以寻找到符合条件的最小右端点,的右端点显然都满足条件，我们直接根据最小右端点的坐标就可以计算左端点满足的区间的个数。左端点向右移动时，右端点显然满足单调性，但我们需要区间查询最大值，最小值，这里用st表实现就行。总复杂度O(nm)。其实仔细思考一下，这里的l，r向右移动时，不就是一直在维护一个区间最值问题吗？而对于区间最值的问题我们也可以用单调队列做啊，只不过我们需要最大值和最小值，需要两个单调队列。
下面是单调队列版本的
//不等,不问,不犹豫,不回头. #include<bits/stdc++.h> #define _ 0 #define ls p<<1 #define db double #define rs p<<1|1 #define P 1000000007 #define ll long long #define get(x) x=read() #define PLI pair<ll,int> #define PII pair<int,int> #define ull unsigned long long #define put(x) printf("%d ",x) #define putl(x) printf("%lld ",x) #define rep(x,y,z) for(int x=y;x<=z;++x) #define fep(x,y,z) for(int x=y;x>=z;--x) #define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y) using namespace std; const int N=1e5+10; int n,m,a[N]; int q1[N],head1,tail1,q2[N],head2,tail2; inline int read() {int x;scanf("%d",&x);return x;} //q1为单点递增，q2为单调递减。 int main() { // freopen("1.in","r",stdin); get(n);get(m); rep(i,1,n) get(a[i]); rep(j,1,m) { int get(k); head1=tail1=head2=tail2=1; q1[1]=q2[1]=1; int l=1; ll ans=0; rep(i,2,n)//尺取法枚举每个右端点。 { while(head1<=tail1&&a[i]<=a[q1[tail1]]) tail1--; while(head2<=tail2&&a[i]>=a[q2[tail2]]) tail2--; q1[++tail1]=i;q2[++tail2]=i; while(1)//向左一直移动左端点。 { while(head1<=tail1&&q1[head1]<l) ++head1; while(head2<=tail2&&q2[head2]<l) ++head2; if(a[q2[head2]]-a[q1[head1]]>k) { ans+=n-i+1; ++l; } else break; } } putl(ans); } return (0^_^0); } //以吾之血,铸吾最后的亡魂.
简化题意：给你n个盒子，每个盒子里面有一个球，球的颜色要么为黑色，要么为白色，概率为1/2。每个盒子打开需要一定的代价，现你可以申请一个提示，提醒你现在未打开的盒子中黑球的个数。但申请提示人需要一定的代价。问清楚每个盒子中球的颜色的期望代价。
我们先分析这个提示什么时候用最好，由于每次打开盒子我们就知道自己这次打开的盒子中球的颜色，所以我们最初就用提示，每次打开盒子就能知道剩下的球的颜色个数，所以要么不用，要么在最开始用。不用提示，期望为将每个盒子打开的代价和。用提示的话，考虑我们会省下哪些费用，当剩下盒子中的球的颜色同为一个色时，我们根据剩下和的数量和根据提示得到的求颜色的数量相等就能得知剩下的球的全部颜色。我们可以将所有局面划分成在某个点，在这个点之后所有球的颜色相等，可以发现所有可能的情况都能按照以上方法划分到某个局面里。我们可以枚举一个i，当做这个点，i之后的所有球的颜色相等，计算在这种局面下的所有情况的期望值。这种情况的代价是sum[i](sum表示前缀和)。这种局面所有情况的概率和为多少呢？我们注意到一个事情，就是第i个球的颜色必须和之后球的颜色相反，不然在若i的颜色和后面的相同的话这种情况就被划分到i-1了。所以概率为(1/2)^(n-i)。考虑i枚举的范围i为0时，表示所有球的颜色相同，但由于代价为0就不予考虑了。可以思考到i最大到n-1，因为最后一个球我们真的不必去开，肯定能推知它的颜色。并且由于我们可以任意打开宝箱，所以我们可以将所有盒子排序，先打开代价小的一定最优。
//不等,不问,不犹豫,不回头. #include<bits/stdc++.h> #define _ 0 #define ls p<<1 #define db double #define rs p<<1|1 #define P 1000000007 #define ll long long #define INF 1000000000 #define get(x) x=read() #define PLI pair<ll,int> #define PII pair<int,int> #define ull unsigned long long #define put(x) printf("%d ",x) #define putl(x) printf("%lld ",x) #define rep(x,y,z) for(int x=y;x<=z;++x) #define fep(x,y,z) for(int x=y;x>=z;--x) #define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y) using namespace std; const int N=1e5+10; int n; db C,w[N],t[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } int main() { //freopen("1.in","r",stdin); get(n);scanf("%lf",&C); db ans=0;t[0]=1; rep(i,1,n) { scanf("%lf",&w[i]); ans+=w[i];t[i]=t[i-1]*0.5; } sort(w+1,w+n+1); db sum=0,da=C; rep(i,1,n-1)//sum*(1/2)^(n-i) { sum+=w[i]; da+=sum*t[n-i]; } ans=min(ans,da); printf("%.6lf",ans); return (0^_^0); } //以吾之血,铸吾最后的亡魂.
题意就不多说了，其实我们很容易就可以想到枚举i和j，使得Ai<Bj，在这个时候统计答案，我们可以预处理一个f[i][j]表示A串到i，B串到j，的公共子序列的个数，便于我们统计答案。显然的是f[i][j]可以通过DP的方式预处理出来，不过对于我来说这个dp还真的有点难想....我们先考虑f[i][j]一共包含多少种类型的字符串，考虑每种类型的字符串我们怎么得到他们的数量，最后累加上就行。虽然这种方法可能比较笨，但对于某些计数容斥类的题目还是比较清晰的。
对于dp的详解如下：
f[i][j]表示A串到i，B串到j，的公共子序列的个数。 我们考虑将f[i][j]包含的公共字符串分成几类： 1.不以i和j结尾 f[i-1][j-1] 2.以i结尾，不以j结尾 f[i][j-1]-f[i-1][j-1] 3.以j结尾，不以i结尾 f[i-1][j]-f[i-1][j-1] 4.以i和j结尾。（ca[i]==cb[j]）f[i-1][j-1]+1 f[i-1][j-1] 包含1 f[i][j-1] 包含1,2 f[i-1][j] 包含1,3 for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]; if(ca[i]==cb[j]) f[i][j]+=f[i-1][j-1]+1;//所有非i和j结尾的公共子序列接个i和j的后缀 } //构成新的字符串，并且单独i和j
对于前面的答案有了想法之后对于后面的怎么选，考虑A串后面还有n个字母，B串后面还有m个字母，假设n>=m我们能选的方案为Cn 0*Cm 0+Cn1*cm1+Cn2*Cm2+...+Cn m*Cm m这个方案数怎么求呢？
考虑将等式做一个转换，原等式=Cn 0*Cm m+Cn 1*Cm m-1+...+Cn m*Cm 0,这个等式可以理解为我们现在有两堆球，第一堆球的个数为n，第二堆球的个数为m个，我们每次从第二堆球中取出k个,（0<=k<=m），再从第一堆球中取出m-k个，一共的方案数，由于每次取出来的球的总数一定为m，所以我们可以将两队球的数量合并，总的方案数就为C(n+m) m，其实我们可以发现从n+m个球中取出m个，所有包含的情况就是从第二堆中取出0，1,2,...m个。发现两者是等效的。这里用阶乘预处理下即可。
//不等,不问,不犹豫,不回头. #include<bits/stdc++.h> #define _ 0 #define ls p<<1 #define db double #define rs p<<1|1 #define P 1000000007 #define ll long long #define INF 1000000000 #define get(x) x=read() #define PLI pair<ll,int> #define PII pair<int,int> #define ull unsigned long long #define put(x) printf("%d ",x) #define putl(x) printf("%lld ",x) #define rep(x,y,z) for(int x=y;x<=z;++x) #define fep(x,y,z) for(int x=y;x>=z;--x) #define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y) using namespace std; const int N=5010,mod=1e9+7; int f[N][N],n,m; ll jc[N<<2],inv_jc[N<<2]; char A[N],B[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline ll power(ll a,int b) { ll ans=1; while(b) { if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans%mod; } inline void prework() { rep(i,1,n) rep(j,1,m) { f[i][j]=((f[i-1][j]+f[i][j-1])%mod-f[i-1][j-1]+mod)%mod; if(A[i]==B[j]) f[i][j]=(f[i][j]+f[i-1][j-1]+1)%mod; } jc[0]=1;inv_jc[0]=1; rep(i,1,n+m) { jc[i]=jc[i-1]*i%mod; inv_jc[i]=inv_jc[i-1]*power(i,mod-2)%mod; } } inline ll C(int n,int m) { return jc[n]*inv_jc[m]%mod*inv_jc[n-m]%mod; } int main() { // freopen("1.in","r",stdin); scanf("%s",A+1);scanf("%s",B+1); n=strlen(A+1);m=strlen(B+1); prework(); ll ans=0; rep(i,1,n) rep(j,1,m) { if(A[i]<B[j]) { ans=(ans+(ll)(f[i-1][j-1]+1)*C(n-i+m-j,min(n-i,m-j))%mod)%mod; } } putl(ans); return (0^_^0); } //以吾之血,铸吾最后的亡魂.