$$ \text{题意：给定一个括号序列，求插入若干个括号，将这个括号序列变成} \\ \text{长度为}2\times n\text{的括号序列的方案数} \\ \\ \text{一开始考虑阶段设置为当前要在原串第几个字符后面加字符，然后发现根本没法转移}.. \\ \text{然后考虑把阶段设置为，当前放置了几个字符} \\ \text{设}f\left( n,m,k \right) \text{表示当前已经放置完成了}n\text{个字符，使用掉了原串的前}m\text{个字符} \\ \text{已经放置好了的字符串中，左括号比右括号多}k\text{个} \\ \text{时候的方案数} \\ \text{首先是边界条件}f\left( \text{0,0,}0 \right) =1 \\ \text{因为空串只有一种方案} \\ \text{转移时，首先考虑当前位置是左括号还是右括号。} \\ \text{然后如果这时候可以使用原串中的字符来完成转移，那么要优先使用原串字符} \\ \text{除非原串的字符不能完成这次转移，再去考虑加入新的字符} \\ \text{左括号时:} \\ f\left( n,m,k \right) =f\left( n,m,k \right) +f\left( n-\text{1,}m-\text{1,}k-1 \right) \left( \text{原串第}m\text{位置为左括号} \right) \\ f\left( n,m,k \right) =f\left( n,m,k \right) +f\left( n-\text{1,}m,k-1 \right) \left( \text{原串第}m\text{位置不是左括号} \right) \\ \text{右括号时:} \\ f\left( n,m,k \right) =f\left( n,m,k \right) +f\left( n-\text{1,}m-\text{1,}k+1 \right) \left( \text{原串第}m\text{位置为右括号} \right) \\ f\left( n,m,k \right) =f\left( n,m,k \right) +f\left( n-\text{1,}m,k+1 \right) \left( \text{原串第}m\text{位置不是右括号} \right) \\ \text{最后答案放置了}2\times n\text{个字符，使用了原串的全部字符，左括号比右括号多0个的方案数} $$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <string>
#include <map>
#include <cstring>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t mod = 1000000007;
const int_t LARGE = 300;
char buff[LARGE + 10];
int_t val[LARGE + 1];
int_t prefix[LARGE + 1];
int_t dp[LARGE + 1][LARGE + 1][LARGE + 1];
int_t n;
int_t len;

void inc(int_t& x,int_t p) {
	x = (x % mod + p + 2 * mod) % mod;
}

int main() {
	freopen("regular.in","r",stdin);
	freopen("regular.out","w",stdout);

	cin >> n;
	scanf("%s",buff + 1);
	len = strlen(buff + 1);
	for(int_t i = 1; i <= len; i++) {
		if(buff[i] == '(') val[i] = 1;
		else val[i] = -1;
		prefix[i] = prefix[i - 1] + val[i];
	}
	dp[0][0][0] = 1;
	for(int_t i = 1; i <= 2 * n; i++) {
		for(int_t j = 0; j <= std::min(i,len); j++) {
			for(int_t k = 0; k <= i; k++) {
				//×óÀ¨ºÅ
				if(val[j]==1&&k-1>=0&&j>0){
					inc(dp[i][j][k],dp[i-1][j-1][k-1]);
				} else{
					if(k-1>=0)inc(dp[i][j][k],dp[i-1][j][k-1]);
				}
				//ÓÒÀ¨ºÅ 
				if(val[j]==-1&&j>0){
					inc(dp[i][j][k],dp[i-1][j-1][k+1]);
				} else{
					inc(dp[i][j][k],dp[i-1][j][k+1]);
				}
				continue;
			}
		}
	}
	cout<<dp[2 * n][len][0]<<endl;
	return 0;
}

$$ \text{设}f\left( n,m,k,d \right) \text{表示走到了格子}\left( n,m \right) \text{，} \\ \text{小}a\text{采集的魔液与}uim\text{采集的魔夜的差为}k\text{，这一步是小}a\text{还是}uim\text{采集的方案数} \\ \text{初始时,}f\left( n,m,mat_{n,m},1 \right) =\text{1\ }\left( \text{要求可以从任意点出发} \right) \\ \text{转移时} \\ f\left( n+\text{1,}m,k+mat_{n+\text{1,}m},0 \right) +=f\left( n,m,k,1 \right) \\ f\left( n,m+\text{1,}k+mat_{n,m+1},0 \right) +=f\left( n,m,k,1 \right) \\ f\left( n+\text{1,}m,k-mat_{n+\text{1,}m},1 \right) +=f\left( n,m,k,0 \right) \\ f\left( n,m+\text{1,}k-mat_{n,m+1},1 \right) +=f\left( n,m,k,0 \right) \\ \text{最后答案为所有}f\left( n,m,\text{0,}1 \right) \text{的和。} \\ $$

#include <iostream>
using int_t = int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1000000007;

int_t n, m, k;
//走到了n行m列，a与uim的差为k，最后一步0：a，1：uim的方案数
int_t f[802][802][16][2];
int_t mat[802][802];

inline void inc(int_t &x, int_t b)
{
    x = ((x + b) % mod + mod) % mod;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    k += 1;
    for (int_t i = 1; i <= n; i++)
    {
        for (int_t j = 1; j <= m; j++)
        {
            scanf("%d", &mat[i][j]);
            f[i][j][mat[i][j]][0] = 1;
        }
    }
    int_t result = 0;
    for (int_t i = 1; i <= n; i++)
    {
        for (int_t j = 1; j <= m; j++)
        {
            for (int_t k = 0; k < ::k; k++)
            {
                //下一步是a
                inc(f[i + 1][j][(k + mat[i + 1][j]) % ::k][0], (f[i][j][k][1]));
                inc(f[i][j + 1][(k + mat[i][j + 1]) % ::k][0], (f[i][j][k][1]));
                //下一步是uim
                inc(f[i + 1][j][(k - mat[i + 1][j] + ::k) % ::k][1], f[i][j][k][0]);
                inc(f[i][j + 1][(k - mat[i][j + 1] + ::k) % ::k][1], f[i][j][k][0]);
            }
            inc(result, f[i][j][0][1]);
        }
    }
    printf("%d", result);
    return 0;
}

我我我我没救了吧…

现在普及难度的题还能写1h…

我..

单调队列优化DP，或者线段树优化。

$$f\left( n \right) =A_n+\max _{n-r\le i\le n-l}f\left( i \right) $$

后面的那个max显然可以用单调队列来维护。

从前向后枚举状态，每次枚举到一个位置，先把因为枚举到这个位置而能够使用的最新的状态扔到单调队列(即i-left，因为i-left在枚举到状态i之前一定不会用到)，然后从队列头删掉不合法的状态。

#include <iostream>
#include <algorithm>

using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 200000;

int_t A[LARGE * 2 + 1];
int_t f[LARGE * 2 + 1];

int_t queue[LARGE * 3 + 1];
int_t tail = 0;
int_t head = 0;

int_t left, right;
int_t n;

const int_t INF = 0x7fffffff;

int main()
{
    cin >> n >> left >> right;
    for (int_t i = 0; i <= n; i++)
        cin >> A[i];
    //构造队列，使得队头的元素解最优
    queue[tail++] = 0;
    for (int_t i = 1; i <= n + right; i++)
    {
        //加入新取到的元素
        if (i - left >= 0)
        {
            while (tail > head && f[queue[tail - 1]] < f[i - left])
            {
                tail--;
            }
            queue[tail++] = i - left;
        }
        while (tail > head && queue[head] < i - right)
        {
            head++;
        }

        if (tail > head && queue[head] <= i - left)
        {
            f[i] = A[i] + f[queue[head]];
        }
    }
    int_t result = -INF;
    for (int_t i = n + 1; i <= n + right; i++)
        result = std::max(result, f[i]);
    cout << result << endl;
    return 0;
}

很简单的斜率优化题（捂脸）

$$ \text{状态转移方程} \\ f\left( k,n \right) \text{表示在前}n\text{个数中切了}k\text{刀的最优解} \\ \left( \text{对于}n\le k\text{或者}k=\text{0,结果为}0 \right) \\ \text{设}S_n=\sum_{1\le i\le n}{a_i} \\ f\left( k,n \right) =MAX_{1\le i\le n-1}f\left( k-\text{1,}i \right) +\left( S_n-S_i \right) S_i \\ \text{以}k\text{为阶段进行转移} \\ \text{在从}k-\text{1转移到}k\text{时，维护一个单调队列，从队尾到队首的解越来越差} \\ \text{如何构造这个单调队列？} \\ \text{假设单调队列中的所有的元素已经有序，设其中最后的两个元素的}n\text{的取值为}i,j\ \text{设我们要加入到队列的元素的}n\text{的取值为}k \\ \text{设}g\left( x \right) =f\left( k-\text{1,}x \right) -S_{x}^{2} \\ \text{以为单调队列前面的元素比后面的优，所以}i\text{是比}j\text{优的} \\ \text{假如现在}k\text{还比}j\text{优，那么我们显然可以直接把}j\text{扔了，因为它没用} \\ \text{考虑什么时候}k\text{比}j\text{优} \\ \text{如果}i\text{比}j\left( i<j \right) \text{优，那么一定有} \\ f\left( k-\text{1,}i \right) +S_nS_i-S_{i}^{2}>f\left( k-\text{1,}j \right) +S_nS_j-S_{j}^{2} \\ \text{整理一下} \\ f\left( k-\text{1,}i \right) -S_{i}^{2}-\left( f\left( k-\text{1,}j \right) -S_{j}^{2} \right) >S_n\left( S_j-S_i \right) \\ g\left( i \right) -g\left( j \right) >S_n\left( S_j-S_i \right) \\ i<j,\text{所以}S_i<S_j\ \left( S_n\text{单调不降} \right) \\ \text{所以不等式不要变号} \\ \frac{g\left( i \right) -g\left( j \right)}{S_j-S_i}>S_n \\ \text{两边取负} \\ \frac{g\left( i \right) -g\left( j \right)}{S_i-S_j}<-S_n \\ \text{同理，如果}k\text{优于}j\text{，那么我们可以得到} \\ \frac{g\left( k \right) -g\left( j \right)}{S_k-S_j}>-S_n \\ \text{所以我们可以得到，如果}i\text{优于}j\text{而且}k\text{优于}j\left( \text{这个情况应该扔掉}j \right) \ i,j,k\text{应该满足的条件是} \\ \frac{g\left( k \right) -g\left( j \right)}{S_k-S_j}>\frac{g\left( i \right) -g\left( j \right)}{S_i-S_j} \\ \text{即}k,j\text{所构成的直线的斜率大于}i,j\text{所构成的直线的斜率} \\ \text{所以在压入元素}k\text{时，我们需要一直判断直线}ij\text{和直线}jk\text{的斜率关系，如果满足直线}jk\text{的斜率大于直线}ij\text{的斜率，那么我们就需要扔掉点}j \\ \text{一直重复，直到队列中只剩下一个点或者}jk\text{的斜率小于等于}ij\text{的斜率} \\ \text{同时，每个}n\text{的取值在计算时，我们要做的是从队列头取元素} \\ \text{然而}i<j\text{且}i\text{优于}j\text{的条件是} \\ \frac{g\left( i \right) -g\left( j \right)}{S_i-S_j}<-S_n \\ \text{所以我们需要保证队头的元素满足这个关系} \\ \text{所以我们每次考虑队头的两个元素}i,j\text{，如果不满足这个关系，那么就扔掉}i\text{，因为这个时候}i\text{不可能比}j\text{优} \\ \text{然后转移即可} \\ \text{单调队列中的点构成了一个上凸壳，相邻两点所连成的直线，从左到右满足斜率单调不升} \\ \\ $$

#include <iostream>
#include <algorithm>
#include <deque>
#include <cstring>
using int_t = long long int;
using real_t = long double;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 100000;
int_t sum[LARGE + 1];
int n, k;
const real_t EPS = 1e-12;
struct Point
{
    //g(pos)
    real_t value;
    //n的取值
    int_t pos;
    Point(real_t val = 0, int_t pos = 0)
    {
        this->value = val;
        this->pos = pos;
    }
};

real_t scope(const Point &a, const Point &b)
{
    if (sum[a.pos] == sum[b.pos])
        return (real_t)(a.value - b.value) / EPS;
    return (real_t)(a.value - b.value) / (real_t)(sum[a.pos] - sum[b.pos]);
}
int_t dp[201][LARGE + 1];
int_t path[201][LARGE + 1];
Point queue[LARGE * 2 + 1];
int main()
{
    scanf("%d%d", &n, &k);
    for (int_t i = 1; i <= n; i++)
    {
        scanf("%lld", &sum[i]);
        sum[i] += sum[i - 1];
    }

    //左闭右开区间
    int_t head = 0;
    int_t tail = 0;
    for (int_t k = 1; k <= ::k; k++)
    {
        //每次开始时清空队列
        head = tail = 0;
        //把唯一一个合法的点扔进去
        queue[tail] = Point(dp[k - 1][k] - sum[k] * sum[k], k);
        tail++;
        for (int_t n = k + 1; n <= ::n; n++)
        {
            /*
            g(n)=f(k-1,n)-S(n)^2
            */
            //弹出不合法的元素
            while (tail - head >= 2 && scope(queue[head], queue[head + 1]) >= -sum[n])
                head++;
            //写结果
            int_t prev = queue[head].pos;
            dp[k][n] = dp[k - 1][prev] + (sum[n] - sum[prev]) * sum[prev];
#ifdef DEBUG
            cout << "(k=" << k << " n= " << n << ")=" << dp[k][n] << " from (k=" << k - 1 << " n= " << prev << ") = " << dp[k - 1][prev] << endl;
#endif
            path[k][n] = prev;
            //加入新的元素
            Point curr(dp[k - 1][n] - sum[n] * sum[n], n);
            while (tail - head >= 2 && (sum[curr.pos] == sum[queue[tail - 1].pos] || scope(curr, queue[tail - 1]) >= scope(queue[tail - 1], queue[tail - 2])))
            {
                tail--;
            }
            queue[tail] = curr;
            tail++;
        }
#ifdef DEBUG
        cout << endl;
#endif
    }

    printf("%lld\n", dp[k][n]);
    int_t id = path[k][n];
    for (int_t k = ::k; k >= 1; k--)
    {
        printf("%lld ", id);
        id = path[k - 1][id];
    }
    return 0;
}