P7777 『JROI-2』Shelter - 题解
CSP_Sept
·
·
题解
题号 7777 留念（
Description
给定 n，要求把 1\sim n 取完，有两种取法：
- 单独取 i，代价 i\times p。
- 一起取 i,j，代价 |i-j|\times q。
求最小代价。
Solution
首先观察到两个显然的性质：
- 开始使用方法 2 后，一直使用方法 2 是最优的。
- 使用方法 2 时，保证 |i-j|=1 是最优的。
我们考虑何时开始使用方法 2。
对于 i,i+1，有两种代价：(2i+1)\times p 和 q。
于是，当 (2i+1)\times p\ge q 且 n-i-1 为偶数时，我们就开始使用方法 2。
### Code
```cpp
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
ll p, q, n;
void sol(){
scanf("%lld%lld%lld", &n, &p, &q);
if(p == 0){
puts("0");
return;
}
if(n == 1){
printf("%lld\n", p);
return;
}
ll x = q / p;
x = (x - 1) / 2;
ll res = n - x;
ll ans = 0;
if(res % 2) x++, res--;
ans = x * p;
ans += (x - 1) * x * p / 2;
ans += (res / 2) * q;
printf("%lld\n", ans);
}
int main(){
//freopen("tmp.in", "r", stdin);
//freopen("tmp.out", "w", stdout);
int t;
scanf("%d", &t);
while(t--) sol();
return 0;
}
```