BoundedOptimization TopCoder

BoundedOptimization TopCoder - 12294

考虑在最优情况下，某一些数在( ext{lowerbound}),某一些在( ext{upperbound})

确定了这些数之后，对于那些处于(( ext{lowerbound,upperbound}))之间的数，它们的值其实是在忽略了上下界的情况下能取到的最优情况

否则只要上下移动一点就可能达到一个更优的情况

那么考虑枚举每个数的状态在( ext{lowerbound,upperbound,(lowerbound,uppperbound)})

推论：在中间的数之间必然存在互相关系

假设存在两个数(x_i,x_j)之间没有互相关系，令其他数不变，

则答案式子可以表示为(ax_i+bx_j+c)的形式，改变两个数的值总能得到更优的情况

[ ]

设处在中间位置的数为(x_1,cdots,x_m)，其他数为(y_1,cdots ,y_k)，每个数连到外面的权值总和为(s_i)

发现在最优情况下，(sum x_i+sum y_i =MaxSum)，那么就确定了(sum x_i)的值，设为(Sum)

那么答案就可以表示为(egin{aligned}frac{sum_ix_icdot(Sum-x_i+2cdot s_i)}{2}end{aligned}+c)

其中常数(c)是外面的数之间的总和

不考虑限制的情况下，最优情况是(x_i=frac{Sum+s_i}{2})

此时，若(sum x_i e Sum)，是不合法的，需要调整

而让每个数改变(d)，减少的答案都是(d^2)(因为原来是在二次函数的最高点)

所以每个数都改变(egin{aligned}frac{sum frac{Sum+x_i}{2}-Sum}{m}end{aligned})是最优的

注意这里计算时都是忽略了(x_1,cdots,x_m)的( ext{lowerbound,upperbound})，求出的值不一定合法

如果不合法说明至少有某个值该到上下界之后答案会更优，所以这次的答案不用考虑

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

const int N=30;
const db eps=1e-7;

int G[N][N];
int A[N],w[N];
db val[N];

class BoundedOptimization {
public:
	double maxValue(vector <string> Expr, vector <int> L, vector <int> R, int Max) {
		string E="";
		for(string t:Expr) E+=t;
		memset(G,0,sizeof G);
		rep(i,0,E.size()-1) if(isalpha(E[i])) {
			G[E[i]-'a'][E[i+1]-'a']=G[E[i+1]-'a'][E[i]-'a']=1;
			i++;
		}
		int n=L.size();
		db ans=0;
		rep(S,0,pow(3,n)-1) {
			int T=S,m=0;
			db res=0,sum=0;
			rep(i,0,n-1) {
				w[i]=T%3;
				if(!w[i]) A[++m]=i;
				else val[i]=(w[i]==1?L[i]:R[i]),sum+=val[i];
				T/=3;
			}
			int fl=sum<=Max;
			rep(i,1,m) rep(j,i+1,m) if(!G[A[i]][A[j]]) fl=0;
			if(!fl) continue;
			db left=Max-sum; 
			rep(i,1,m) {
				db c=left;
				rep(j,0,n-1) if(w[j] && G[A[i]][j]) c+=val[j]*2;
				val[A[i]]=c/2;
				sum+=val[A[i]];
			}
			if(m){
				db t=(sum-Max)/m;
				rep(i,1,m) val[A[i]]-=t;
			}
			rep(i,0,n-1) if(val[i]<L[i]-eps || val[i]>R[i]+eps) fl=0;
			if(!fl) continue;
			rep(i,0,n-1) rep(j,i+1,n-1) if(G[i][j]) res+=val[i]*val[j];
			cmax(ans,res);
		}
		return ans;	
	}
};