P2134 百日旅行

题目背景

重要的不是去哪里，而是和你在一起。——小红

对小明和小红来说，2014年7月29日是一个美好的日子。这一天是他们相识100天的纪念日。

（小明：小红，感谢你2场大考时默默的支持，100个日夜的陪伴；感谢你照亮我100个美好的日子，给我留下无数美好的回忆……在这个美好的日子里，我准备带你去旅行。）

题目描述

小明和小红还剩下N天的假期，小明可以安排旅行的计划。如果连续X天旅游，小明需要花旅行费用P*X*X元；如果连续X天不旅游，小明需要请小红吃饭，花费为Q*X元。（P,Q都是输入的常数）

请你帮小明写一个程序，计算出假期里他至少需要花费多少元。

输入输出格式

输入格式：

一行，3个空格隔开的正整数N，P，Q。

输出格式：

一行，一个正整数表示小明至少需要花费多少元。

输入输出样例

输入样例#1：

6 1 7

输出样例#1：

说明

对于20%数据，N<=20。

对于90%数据，N<=1000,P<=2000,Q<=10000.

对于剩下的10%数据，N<=200000,Q<=P<=10000。

——————————————————————————————————————————————————————————————

线性DP……$O(N^2)$做法显然

f[i][1/0] 表示前i天旅行的最小费用，第i天是吃饭（0）或旅游（1）

枚举j，状态转移方程为

$f[i][1]=min(f[j][1]+p*(i-j)^2)$

$f[i][0]=min(f[j][0]+q*(i-j))$

考虑优化。

观察发现，吃饭每天花费的费用是一个不变的定值，由此我们可以想到两点。

1.f[i][0]可以做到$O(1)$转移

2.旅游花费的费用显然是递增的，当旅游费用大于吃饭费用，不如去吃饭。

复杂度为$O(能过)$

code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#define R register

typedef long long LL;
const int MAXN = 200010;
int n, p, q;
LL f[MAXN][2];
//f[i][1/0] 表示前i天旅行的最小费用，第i天是吃饭（0）或旅游（1）

inline int read() {
    int num = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {num = num * 10 + ch - '0'; ch = getchar();}
    return num * f;
}

int main() {
    memset(f, 10, sizeof(f));
    n = read(); p = read(); q = read();
    f[0][0] = f[0][1] = 0;
    for (R int i = 1; i <= n; ++ i) {
        f[i][0] = std::min(f[i-1][1], f[i-1][0]) + q;
        for (R int j = i - 1; j >= 0; -- j) {
            if (p * (i - j) * (i - j) >= q * (i - j)) break;
            f[i][1] = std::min(f[i][1], f[j][0] + p * (i - j) * (i - j));
        }
    }
    std::cout << std::min(f[n][0], f[n][1]) << std::endl;
    return 0;
}

通过发现的两点，我们发现好像这题有贪心解法。

事实上也是如此贪心

不知为何贪心还没DP快