本文共 2028 字，大约阅读时间需要 6 分钟。

可以直接跑差分约束得到合法解的最小解和最大解…但是没有用,求不出方案数

考虑直接把变量看成两个砝码的差值

令$f[i][j]$表示$max(w_i-w_j)$,令$g[i][j]=min(w_i-w_j)$

看作一个$dp$来求解

对于$+$,有$w_i-w_j=1或w_i-w_j=2$

令$f[i][j]=2,g[i][j]=1$

对于$-$,令$f[i][j]=-1$,$g[i][j]=-2$

对于$=$,令$f[i][j]=g[i][j]=0$

对于$?$,令$f[i][j]=2,g[i][j]=-2$

我们需要求$f$每个变量的最大值,在这些约束之下求最短路

使用$floyd$可以松弛$f,g$数组

那么对于$A+B>C+D$可以改写成$A-C>D-B$

那么一定满足$g(A,C)>f(D,B)$,说明是一组合法的解

那么对于$A+B<C+D$可以改写成$A-C<D-B$

那么一定满足$f(A,C)<g(D,B)$,说明是一组合法的解

那么对于$A+B==C+D$可以改写成$A-C==D-B$

那么一定满足$f(A,C)==g(A,C)==f(D,B)==g(D,B)$,说明是一组合法的解

所以直接枚举$C,D$暴力判断即可

#include 
   
    using namespace std;const int N = 55;int n,A,B,mi[N][N],mx[N][N];char a[N][N];int main(){
   	cin >> n >> A >> B;	for(int i=1;i<=n;i++)	cin >> ( a[i]+1 );	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	{
   		if( a[i][j]=='?' )	mi[i][j] = -2, mx[i][j] = 2;		else if( a[i][j]=='+' )	mi[i][j] = 1, mx[i][j] = 2;		else if( a[i][j]=='-' )	mi[i][j] = -2,mx[i][j] = -1;		else if( a[i][j]=='=' )	mi[i][j] = mx[i][j] = 0; 	}	for(int k=1;k<=n;k++)	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	{
   		mi[i][j] = max( mi[i][j],mi[i][k]+mi[k][j] );		mx[i][j] = min( mx[i][j],mx[i][k]+mx[k][j] );	}	int ans1 = 0, ans2 = 0, ans3 = 0;	for(int i=1;i<=n;i++)	for(int j=1;j
    
     C+D		//A-C>D-B或者A-D>C-B 		if( mi[A][i]>mx[j][B] || mi[A][j]>mx[i][B] )	ans1++;		//A+B
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114491268 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！