考虑在最优情况下，某一些数在 \(\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;
}
};
|