uva 11971 - Polygon(线性规划)

本文主要是介绍uva 11971 - Polygon(线性规划)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：uva 11971 - Polygon

题目大意：给定一个长度为N的线段，要求切K刀，分成K+1个线段，问能组成K+1边形的概率。

解题思路：K条线段能组成K边形的条件为任意一条边小于其他所有边的和，因为是求概率，所以和N无关。
根据高中线性规划的知识，以二维为例：

所以有ans=2K−K−12K

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
const int maxn = 60;ll gcd (ll a, ll b) {return b == 0 ? a : gcd(b, a % b);
}int main () {ll f[maxn];f[0] = 1;for (int i = 1; i <= 50; i++)f[i] = f[i-1] * 2;int cas;scanf("%d", &cas);for (int kcas = 1; kcas <= cas; kcas++) {int N, K;scanf("%d%d", &N, &K);printf("Case #%d: ", kcas);if (K == 1)printf("0/1\n");else {ll member = f[K] - K - 1;ll d = gcd(member, f[K]);printf("%lld/%lld\n", member / d, f[K] / d);}}return 0;
}

这篇关于uva 11971 - Polygon(线性规划)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---