考虑在最优情况下，某一些数在$\text{lowerbound}$,某一些在$\text{upperbound}$
确定了这些数之后，对于那些处于$(\text{lowerbound,upperbound})$之间的数，它们的值其实是在忽略了上下界的情况下能取到的最优情况
否则只要上下移动一点就可能达到一个更优的情况
那么考虑枚举每个数的状态在$\text{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$
那么答案就可以表示为$\begin{aligned}\frac{\sum_ix_i\cdot(Sum-x_i+2\cdot s_i)} {2}\end{aligned}+c$
其中常数$c$是外面的数之间的总和
不考虑限制的情况下，最优情况是$x_i=\frac{Sum+s_i} {2}$
此时，若$\sum x_i\ne Sum$，是不合法的，需要调整
而让每个数改变$d$，减少的答案都是$d^2$(因为原来是在二次函数的最高点)
所以每个数都改变$\begin{aligned}\frac{\sum \frac{Sum+x_i} {2}-Sum} {m}\end{aligned}$是最优的
注意这里计算时都是忽略了$x_1,\cdots,x_m$的$\text{lowerbound,upperbound}$，求出的值不一定合法
如果不合法说明至少有某个值该到上下界之后答案会更优，所以这次的答案不用考虑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #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;
}
};
|
