BZOJ 1800 [Ahoi2009]fly 飞行棋

暴力枚举

矩形对角线必定是直径，可以枚举直径，然后算方案数，O(n^2)

也可以直接枚举四个顶点,O(n^4)

#include<cstdio> using namespace std; int sum[23]; int main() { int n; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&sum[i]); sum[i]+=sum[i-1]; } int ans=0; for(int a = 1; a <= n; a++) for(int b = a+1; b <= n; b++) for(int c = b+1; c <= n; c++) for(int d = c+1; d <= n; d++) if(sum[b-1]-sum[a-1]==sum[d-1]-sum[c-1] && sum[c-1]-sum[b-1]==sum[a-1]+sum[n]-sum[d-1]) ans++; printf("%d\n",ans); }