url: https://www.luogu.com.cn/problem/UVA1629

tag:
动态规划，枚举，前缀和

思路：
用 dp[lx][ly][rx][ry] 来记录某一个区间中，为使每一块蛋糕都有樱桃的最小代价。使用dfs来枚举每一种可能性。使用记忆化搜索来减少时间。前缀和快速计算出某一块区域樱桃的数量。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int dp[N][N][N][N];
int p[N][N];
int cs;
int pnum(int lx, int ly, int rx, int ry)
{
    return p[rx][ry] - p[lx - 1][ry] - p[rx][ly - 1] + p[lx - 1][ly - 1];
}
int DP(int lx, int ly, int rx, int ry)
{
    if (pnum(lx, ly, rx, ry) == 0) return 0x3f3f3f3f;
    if (pnum(lx, ly, rx, ry) == 1) return 0;
    int &d = dp[lx][ly][rx][ry];
    if (d != 0x3f3f3f3f) return d;
    for (int i = lx; i < rx; i ++)
        d = min(d, DP(lx, ly, i, ry) + DP(i + 1, ly, rx, ry) + ry - ly + 1);
    for (int i = ly; i < ry; i ++)
        d = min(d, DP(lx, ly, rx, i) + DP(lx, i + 1, rx, ry) + rx - lx + 1);
    return d;
}
int main()
{
    int n, m, k;
    while(scanf("%d%d%d", &n, &m, &k) != EOF && n && m)
    {
        memset(p, 0, sizeof p);
        for (int i = 0; i < k; i ++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            p[a][b] = 1;
        }
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        memset(dp, 0x3f, sizeof dp);
        printf("Case %d: %d\n", ++cs, DP(1, 1, n, m));
    }
    return 0;
}

url: https://www.luogu.com.cn/problem/P2672

tag:
NOIP2015 普及组，贪心，线段树，树状数组，前缀和，动态规划。

思路：
思路都是用贪心的策略，有两种情况，一种是取前x个a最大的客户，第二种是取前x - 1个a最大的客户，然后再从第i到n个中选择距离最远的一个去替换第x个a最大的客户，两种情况取最大值输出即可。如何求呢？这里用动态规划和前缀和来求，具体可以看代码。看其他题解有用线段树来做，但是比较麻烦，就上动规和前缀和了。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
long long sum[N], c[N], h[N];
struct client {
    int s, a;
}Client[N];
bool cmp(client &a, client &b)
{
    return a.a > b.a;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) cin >> Client[i].s;
    for (int i = 1; i <= n; i ++) cin >> Client[i].a;
    sort(Client + 1, Client + 1 + n, cmp);
    for (int i = 1; i <= n; i ++)
    {
        sum[i] = sum[i - 1] + Client[i].a;
        h[i] = max(h[i - 1], (long long)Client[i].s * 2);
    }
    for (int i = n; i >= 1; i --)
    {
        c[i] = max(c[i + 1], 2LL * Client[i].s + Client[i].a);
    }
    for (int i = 1; i <= n; i ++)
    {
        cout << max(sum[i] + h[i], sum[i - 1] + c[i]) << '\n';
    }
    return 0;
}

url: https://www.luogu.com.cn/problem/P2568

tag:
数论，欧拉函数，筛法，前缀和

思路：
假设又两个互质的整数a, b，则gcd(a, b) = 1，那么对于任意的自然数p有gcd(a p, b p) = p。利用这个结论，对于这道题我们可以先求欧拉函数，然后求一遍gcd(a, b) = 1 的前缀和，这里求前缀和的时候注意对于1来说只有(1, 1)之后的其他组都有(a, b)和(b, a)。最后遍历每一个质数，用最大值求一个m，使得max(a, b)不超过m的每一对互质数都乘上一个质数得出一个可能的结果。将这个前缀和加到答案即可。

代码：

#include <iostream>  
#include <vector>  
using namespace std;  
const int N = 1e7 + 10;  
int n, phi[N];  
long long sum[N];  
bool st[N];  
long long res;  
vector<int> primes;  
int main()  
{  
    cin >> n;  
    for (int i = 1; i <= n; i ++) phi[i] = i;  
    st[0] = st[1] = true;  
    for (int i = 2; i <= n; i ++)  
    {  
        if (!st[i])  
        {  
            primes.push_back(i);  
            phi[i] = i - 1;  
        }  
        for (int p : primes)  
        {  
            if (p * i > n) break;  
            st[p * i] = true;  
            if (i % p == 0)  
            {  
                phi[i * p] = phi[i] * p;  
                break;  
            }  
            else  
            {  
                phi[i * p] = phi[i] * (p - 1);  
            }  
        }  
    }  
    sum[1] = 1;  
    for (int i = 2; i <= n; i ++)  
    {  
        sum[i] = sum[i - 1] + phi[i] * 2;  
    }  
    for (int p : primes)  
    {  
        int m = n / p;  
        res += sum[m];  
    }  
    cout << res << endl;  
}

url: https://www.luogu.com.cn/problem/P1083

tag:
差分，前缀和，二分

思路：因为要求第一个不满足要求的订单，所以可以想到用二分。二分查找的是不满足要求的情况。通过订单的编号来查找，因为题目中写道有一个不满足要求的订单，后面就会停止分配，这可以抽象成假如有一个订单不满足，后面的订单一定也不满足，而前面的订单或许会满足，这就给二分提供了二段性。求是否满足条件这一块用到了差分，因为有一个区间加一个数这个标志，我们可以先开一个数组表示假如可以借出教室时每天需要有的教室数。通过前缀和求出这个教室数，然后和每天读入的可以借出的教室数比较，如果大于这个可以借出的教室数则表示不满足要求，返回true（因为求的就是不满足要求的订单的最小值，也就是第一个不满足要求的订单。）最后遍历完都符合则返回false。细节方面，因为求前缀和，用到了加法，然后题目的数据范围比较大，所以为了防止超过int的范围，可以让前缀和数组，也就是差分数组的类型为long long.同时因为是开了long long,所以在求前缀和的过程中反复使用的b数组的初始化就需要变成sizeof(long long) * (n + 1) ,（这里下标从1开始，一共n天所有有n + 1个数）。在输出结果的时候还有一个细节，就是题目说会有完全符合的情况，输出0，这里可以在二分的时候多一个标志，假如一直没有出现check(mid) 返回true的情况就说明完全符合，就输出0，反之，假如有一次check(mid)是true的情况就让这个标志为true，之后输出就输出二分结果即可。

代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int n, m;
long long a[N], b[N];
struct lend {
    int d, s, t;
} Lend[N];
bool check(int x)
{
    memset(b, 0, sizeof(long long) * (n + 1));
    for (int i = 1; i <= x; i ++)
    {
        b[Lend[i].s] += Lend[i].d;
        b[Lend[i].t + 1] -= Lend[i].d;
    }
    for (int i = 1; i <= n; i ++)
    {
        b[i] += b[i - 1];
        if (b[i] > a[i]) return true;
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= m; i ++)
    {
        cin >> Lend[i].d >> Lend[i].s >> Lend[i].t;
    }
    int l = 1, r = m;
    bool res = false;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            res = true;
            r = mid;
        }
        else l = mid + 1;
    }
    if (!res) cout << 0 << endl;
    else cout << -1 << '\n' << l << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2004

tag：
前缀和

思路：
先求前缀和，然后遍历右下端点，求出每个对应的子矩阵的总和，判断是否大于res，如果大的话就更新res和坐标x，y。最后输出x和y即可。

ps：这道题很简单，本来不应该传博客的，但是觉得自己写的好优美，忍不住传一下，以后偶尔可以翻出来看看。真的好优美感觉。

代码：

#include <iostream>
using namespace std;
const int N = 1010;
long long p[N][N];
int n, m , c;
int main()
{
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            cin >> p[i][j];
            p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    long long res = 0, x, y;
    for (int i = c; i <= n; i ++)
        for (int j = c; j <= m; j ++)
        {
            long long tmp = p[i][j] - p[i - c][j] - p[i][j - c] + p[i - c][j - c];
            if (tmp > res)
            {
                res = tmp;
                x = i - c + 1;
                y = j - c + 1;
            }
        }
    cout << x << ' ' << y;
    return 0;
}