首页 > 其他分享 >[动态规划] 线性 dp

[动态规划] 线性 dp

时间：2024-05-11 09:52:08浏览次数：24  
标签：状态 x1 饼干 int rint max 线性 动态 dp

线性 dp

SP15637 GNYR04H

按照编号从小到大摆放所有人

    1. 每个人都只能放在已经存在的某个人的后面
    1. (除第一行外)任何一行的人数都不能比后一行多

状态表示：\(f[a][b][c][d][e]\) 表示第一行 \(a\) 个人，第二行 \(b\) 个人，...，第五行 \(e\) 个人的合法方案数

然后在每个状态下枚举每一行，如果某一行能放入一个人，那么就将当前状态的方案数累加到放入一个人的新方案的方案数中。

总结：设计动态规划的转移方程，不一定要以“如何计算出一个状态”的形式给出，也可以考虑“一个已知状态应该更新哪些后续阶段的未知状态”。

int n, f[N][N][N][N][N];

signed main()
{
    while (cin >> n and n != 0)
    {
        int s[5] = {0};
        for (rint i = 0; i < n; i++) cin >> s[i];
        memset(f, 0, sizeof f);
        f[0][0][0][0][0] = 1;
        for (rint a = 0; a <= s[0]; a++)
          for (rint b = 0; b <= s[1]; b++)
            for (rint c = 0; c <= s[2]; c++)
              for (rint d = 0; d <= s[3]; d++)
                for (rint e = 0; e <= s[4]; e++)
                {
                    int &x = f[a][b][c][d][e];
                    if (a && a - 1 >= b) x += f[a - 1][b][c][d][e];
                    if (b && b - 1 >= c) x += f[a][b - 1][c][d][e];
                    if (c && c - 1 >= d) x += f[a][b][c - 1][d][e];
                    if (d && d - 1 >= e) x += f[a][b][c][d - 1][e];
                    if (e) x += f[a][b][c][d][e - 1];
                }
        cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;
    }
    return 0;
}

AcWing 272. 最长公共上升子序列

设 \(f[i][j]\) 表示 \(a[1]\)~\(a[i]\) 与 \(b[1]\)~\(b[j]\) 可以构成的以 \(b[j]\) 结尾的最长公共上升子序列的长度。

当 \(a[i] ≠ b[j]\) 时，有

\[f[i][j] = f[i - 1][j] \]

当 \(a[i] = b[j]\) 时，有

\[f[i][j] = \max_{0≤k<j,b_k<a_i}{\{ f[i-1][k] \}} + 1 \]

在转移过程中，把满足 \(0≤k<j,b_k<a_i\) 的 \(k\) 构成的集合称为 \(f[i][j]\) 进行状态转移时的决策集合，记为 \(S(i,j)\)。注意到，在第二层循环 \(j\) 从 \(1\) 增加到 \(m\) 事，第一层循环 \(i\) 是一个定值，这使得条件 \(b_k<a_i\) 是固定的。因此，当变量 \(j\) 增加 \(1\) 时，\(k\) 的取值范围从 \(0≤k<j\) 变为 \(0≤k<j+1\)，即整数 \(j\) 可能会进入新的决策集合。

当 \(a_i≤b_j\) 时

\[S(i,j+1)=S(i,j) \]

反之则有

\[S(i,j+1)=S(i,j)⋃\{j\} \]

int n;
int a[N], b[N];
int f[N][N];
//表示 a[1]~a[i] 与 b[1]~b[j] 可以构成的以 b[j] 结尾的最长公共上升子序列的长度。

signed main()
{
    cin >> n;
    a[0] = b[0] = -inf; 
    for (rint i = 1; i <= n; i++) cin >> a[i];
    for (rint i = 1; i <= n; i++) cin >> b[i];

    for (rint i = 1; i <= n; i++)
    {
        int val = 1; 
		//val 是决策集合 S(i, j) 中 f[i - 1][k] + 1 的最大值
        for (rint j = 1; j <= n; j++)
        {
            if (a[i] == b[j]) f[i][j] = val; 
			//f[i][j] = f[i - 1][j] + 1
            else f[i][j] = f[i - 1][j];
            //j 即将变成 j + 1，如果满足 a[i] > b[j]，则将 j 加入新的决策集合
            if(a[i] > b[j]) val = max(val, f[i - 1][j] + 1); //更新新的决策集合中 f[i - 1][k] + 1 的最大值
        }
    }

    int ans = 0; 
    for (rint i = 1; i <= n; i++) ans = max(ans, f[n][i]); 
    cout << ans << endl;

    return 0;
}

对于决策集合中的元素只僧增多不减少的情景，就可以维护一个变量来记录决策集合的当前信息，避免重复扫描降低复杂度。

P2893 Making the Grade G

构造出的序列 \(b\) 需要满足单调性，可以是单调递增也可以是单调递减，这里只需要正着反着各算一次取最小即可。

引理：在满足 $ s$ 最小的前提下，一定存在一种构造方案，使得序列 \(b\) 中的所有数值都在序列 a 中出现过。

依次考虑在完成前 \(i\) 个数的构造时 \(s\) 的最小值。因此我们可以按照
长度从 $1 \(~\) n$ 来对已经处理完的前缀序列进行转移，在转移的过程中，为了确保单调性，还需要知道 \(b[i - 1]\) 的取值。

为了能在转移的同时知道 \(b[i - 1]\) 的取值，我们可以直接用二维的状态来转移。

设 \(f[i][j]\) 表示完成前 \(i\) 个数的构造，其中 \(b[i] = j\) 时，\(s\) 的最小值。

由此得出状态转移方程

\[f[i][j]=\min_{0≤k≤j}{\{ f[i-1][k]+|a_i-j| \}} \]

对序列 \(a\) 中出现的数进行离散化，把 dp 状态中第二维 \(j\) 的范围降低到 \(O(n)\)。本题的转移和上一题非常相似，决策集合只多不少，\(O(1)\) 即可实现转移，时间复杂度 \(O(n^2)\)

int n;
int a[N], b[N]; 
//原序列、离散化序列
int f[N][N]; 
//示完成前 i 个数的构造，其中 b[i] = j 时，s 的最小值

int work()
{
    for (rint i = 1; i <= n; i++) b[i] = a[i]; 
	//将原序列拷贝到离散化序列中
    sort(b + 1, b + 1 + n); 

    for (rint i = 1; i <= n; i++)
    {
        int val = inf; 
		//val 表示所有 f[i - 1][k] 的最小值
        for (rint j = 1; j <= n; j++) //枚举第 i 位的取值
        {
            val = min(val, f[i - 1][j]); 
			//决策集合加入新的 j，需要更新最小的 f[i - 1][k]
            f[i][j] = val + abs(a[i] - b[j]); 
			//状态转移方程 ( j 是离散化后的下标，b[j] 才是要选的值 )
        }
    }

    int ans = inf; 
	//记录最小值 s
    for (rint i = 1; i <= n; i++) ans = min(ans, f[n][i]); 
	//从第 n 位的所有取值中取最小值
    return ans;
}

signed main()
{
    cin >> n;
    for (rint i = 1; i <= n; i++) cin >> a[i];
    int res1 = work(); //构造递增序列的最小值
    reverse(a + 1, a + 1 + n); //将序列颠倒
    int res2 = work(); //构造递减序列的最小值
    cout << min(res1, res2) << endl; //两种情况取最小值
    return 0;
}

SP703 SERVICE

可以发现本题 \(dp\) 的 "阶段" 就是 "已经完成的请求数量"，通过指派一个员工，可以把一个 "完成 \(i-1\) 个请求" 的状态
转移到 "完成 \(i\) 个请求" 的状态。

为了计算指派员工的花费，在转移时我们还需要知道每个服务员的位置，由于员工的数量不多，因此最直接的方法就是将
三个员工的位置也存储在每个状态中。

设 \(f[i][x][y][z]\) 表示已经完成了第 \(i\) 个请求，三个员工分别在 \(x, y, z\) 时的最小花费。

我们只需要考虑 \(f[i][x][y][z]\) 能更新哪些状态，很显然， 能更新的状态只有三种，即指派哪个员工去完成请求：

设 \(p[i]\) 表示第 i 个请求所在的位置

\[f[i + 1][p[i + 1]][y][z] = min{ f[i + 1][p[i + 1]][y][z], f[i][x][y][z] + c(x, p[i + 1]) } \]

\[f[i + 1][x][p[i + 1]][z] = min{ f[i + 1][x][p[i + 1]][z], f[i][x][y][z] + c(y, p[i + 1]) } \]

\[f[i + 1][x][y][p[i + 1]] = min{ f[i + 1][x][y][p[i + 1]], f[i][x][y][z] + c(z, p[i + 1]) } \]

可以发现，在第 \(i\) 个请求完成时，一定有某个员工位于 \(p[i]\)，我们只需要记录另外两个员工的位置即可。由此能降一维。

设 \(f[i][x][y]\) 表示已经完成了第 \(i\) 个请求，三个员工分别在 \(p[i], x, y\) 时的最小花费。

根据和上面类似的方式，这里同样有三种更新状态。

\[f[i + 1][x][y] = min{ f[i + 1][x][y], f[i][x][y] + c(p[i], p[i + 1]) } \]

\[f[i + 1][p[i + 1]][y] = min{ f[i + 1][p[i]][y], f[i][x][y] + c(x, p[i + 1]) } \]

\[f[i + 1][x][p[i + 1]] = min{ f[i + 1][x][p[i]], f[i][x][y] + c(y, p[i + 1]) } \]

还需要定义初始状态，最开始三个员工分别在 \(1, 2, 3\)，不妨设 \(p[0] = 3\)，那么初值可设 \(f[0][1][2] = 0\)，目标为 \(f[n][?][?]\)。

注意，本题要求同一位置不能出现两个员工，所以转移的过程中还需要特判状态的合法性。

总结：

  • 1.若阶段不足以表示一个状态，可以把所需的附加信息也作为状态的维度

  • 2.要选择最小的能够覆盖整个状态空间的维度。

int n, m;
int d[N][N]; 
int p[M]; 
//p[i] 表示第 i 个请求所在的位置
int f[M][N][N]; 
//f[i][x][y] 表示已经完成了第 i 个请求，三个员工分别在 p[i], x, y 时的最小花费。

signed main()
{
	int T;
	cin >> T;
	while (T--)
	{
	    cin >> n >> m;
	    memset(d, 0, sizeof d);
	    memset(p, 0, sizeof p);
	    for (rint i = 1; i <= n; i++)
	        for (rint j = 1; j <= n; j++)
	            cin >> d[i][j];
	    for (rint i = 1; i <= m; i++) cin >> p[i];
	    memset(f, 0x3f, sizeof f);
	    p[0] = 3;
	    f[0][1][2] = 0;
	    for (rint i = 0; i < m; i++)
	    {
	        for (rint x = 1; x <= n; x++)
	        {
	            for (rint y = 1; y <= n; y++)
	            {
	                int z = p[i], u = p[i + 1];
	                if(x == z || x == y || y == z) continue; 
	                f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + d[z][u]);
	                f[i + 1][z][y] = min(f[i + 1][z][y], f[i][x][y] + d[x][u]);
	                f[i + 1][x][z] = min(f[i + 1][x][z], f[i][x][y] + d[y][u]);
	            }				
			}
		}
	    //从所有完成请求的方案中取花费最小值
	    int res = inf;
	    for (rint x = 1; x <= n; x++) //枚举完成所有请求时剩下两个员工所在的位置
	    {
	        for (rint y = 1; y <= n; y++)
	        {
	            int z = p[m];
	            if(x == z || x == y || y == z) continue; 
	            res = min(res, f[m][x][y]); 
	        }		
		}
	    cout << res << endl;	
	}
    return 0;
}

P1006 传纸条

按照每一步来看，本题的每个位置都是一个二维坐标，因此考虑每个状态用两个二维坐标表示，得出初步的状态表示。

设 \(f[x_1][y_1][x_2][y_2]\) 表示第一条路径走到 \((x_1, y_1)\)，第二条路经走到 \((x_2, y_2)\) 时的最大价值

但是这里有个问题，我们没法限制每条路径的长度，因为两条路径是同时走的，我们没法保证两个路径同时到终点，而且两条路径可能存在重合，我们没法保证两条路径不会重合。

因此还需要加入一个限制条件，可以发现限制条件就是长度，保证当前状态两条路径都只走了 \(i\) 步。

但是这样就有 $5 $ 个属性需要存储，五维状态过于复杂，我们可以挖掘一下其中的性质来进行优化。

由于两条路径当前都只走了 \(i\) 步，因此 \(x_1 + y_1 = x_2 + y_2 = i\)，即 \(y_1 = i - x_1, y_2 = i - x_2\)

可以发现，由于只能往右走或往下走，所以我们只需要知道横坐标或纵坐标，另一个坐标可以直接计算得出，因此可以降两维。

设 $f[i][x1][x2] $ 表示第一条路径走到 \((x_1, i - x_1)\)，第二条路经走到 \(（x_2, i - x_2)\) 时的最大价值

每条路径都有向右、向下两种走法，所以每个状态有四种转移方式，

设 \(w[x][y]\) 表示 \((x, y)\) 上的物品价值

\[f[i][x_1][x_2] = max{ f[i][x_1][x_2], f[i - 1][x_1 - 1][x_2 - 1] + w } \]

\[f[i][x_1][x_2] = max{ f[i][x1][x_2], f[i - 1][x_1 - 1][x_2] + w } \]

\[f[i][x_1][x_2] = max{ f[i][x1][x_2], f[i - 1][x_1][x_2 - 1] + w } \]

\[f[i][x_1][x_2] = max{ f[i][x1][x_2], f[i - 1][x_1][x_2] + w } \]

最开始两个路径都从 \((1, 1)\) 开始，因此初始状态为 \(f[2][1][1] = 0\)，结束状态为 \(f[n + m][n][n]\)

int n, m;
int w[N][N]; 
//w[i][j] 表示 (i, j) 位置上的价值
int f[N + N][N][N]; 
//f[i][x1][x2] 表示第一条路径走到 (x1, i - x1)，第二条路经走到 （x2, i - x2) 时的最大价值

signed main()
{
    cin >> n >> m;
    for (rint i = 1; i <= n; i++)
        for (rint j = 1; j <= m; j++)
            cin >> w[i][j];

    memset(f, -0x3f, sizeof f);
    f[2][1][1] = 0;

    for (rint i = 2; i <= n + m; i++)
    {
        for (rint x1 = 1; x1 <= n; x1++)
        {
            for (rint x2 = 1; x2 <= n; x2++)
            {
                int y1 = i - x1, y2 = i - x2;
                if (y1 < 1 || y1 > m || y2 < 1 || y2 > m) continue; 
                int t = w[x1][y1];
                if (x1 != x2 || i == 2 || i == n + m) 
				//除了起点和终点，其他时候两条路径不能走到同一个格子上
                {
                    t += w[x2][y2];
                    int &x = f[i][x1][x2];
                    //状态转移方程
                    x = max(x, f[i - 1][x1 - 1][x2 - 1] + t);
                    x = max(x, f[i - 1][x1 - 1][x2] + t);
                    x = max(x, f[i - 1][x1][x2 - 1] + t);
                    x = max(x, f[i - 1][x1][x2] + t);
                }
            }			
		}		
	}

    cout << f[n + m][n][n] << endl;

    return 0;
}

AcWing 276. I-区域

从上往下看它的左端点下标先递减后递增右端点下标先递增后递减, 从上往下看，它的左端点下标先递减后递增，右端点下标先递增后递减。

设 \(f[i,j,l,r,0/1,0/1]\) 表示当前为第 \(i\) 行，已经用了 \(j\) 个格子，凸连通块在第 \(i\) 行的左端点为 \(l\)，右端点为 \(r\)，左端点现在在递增 \((0)\) 还是递减 \((1)\)，右端点在递增 \((0)\) 还是递减 \((1)\)。那么可以列出状态转移方程：

\[len=r-l+1 \]

\[f[i][j][l][r][1][0]=\sum_{p=l}^{r}a[i][p]+max_{l≤p≤q≤r}{\{}f[i-1][j-len][p][q][1][0]{\}}\\ \]

\[f[i][j][l][r][1][1]=\sum_{p=l}^{r}a[i][p]+max_{l≤p≤r≤q}{\{}max_{0≤y≤1}{\{}f[i-1][j-len][p][q][1][y]{\}}{\}}\\ \]

\[f[i][j][l][r][0][0]=\sum_{p=l}^{r}a[i][p]+max_{p≤l≤q≤r}{\{}max_{0≤x≤1}{\{}f[i-1][j-len][p][q][x][0]{\}}{\}}\\ \]

\[f[i][j][l][r][0][1]=\sum_{p=l}^{r}a[i][p]+max_{p≤l≤r≤q}{\{}max_{0≤x≤1}{\{}max_{0≤y≤1}{\{}f[i-1][j-len][p][q][x][y]{\}}{\}}{\}} \]

目标状态：\(max\{f(i,K,l,r,x,y)\}\)。

时间复杂度为 \(O(N * M^4 * K)\)

int n, m, k;
int a[N][N], s[N][N]; 
//a 表示原数组，s 表示每一行的前缀和数组
// f[i][j][l][r][x][y] 表示前 i 行选择了 j 个格子，其中第 i 行选择了第 l 到 r 个格子（若不选均为 0），
// 左边界的单调性类型为 x，右边界的单调性类型为 y（0 表示递增，1 表示递减）时，能构成的凸连通块的最大权值和。
int f[N][M][N][N][2][2];
int res;
//记录最大价值
//pre 记录所有状态的前驱状态，ans 记录最优的结束状态
struct Pre
{
    int i, j, l, r, x, y;
} pre[N][M][N][N][2][2], ans;
// f[i][j][l][r][x][y] 表示当前需要更新的状态
// f[i - 1][j - (r - l + 1)][L][R][X][Y] 表示当前状态的前驱状态
// w 表示当前转移过来的价值

void turn(int i, int j, int l, int r, int x, int y, int L, int R, int X, int Y, int w)
{
    if (w <= f[i][j][l][r][x][y]) return; 
	//只有 > 记录的价值才需要更新
    
	//更新
    f[i][j][l][r][x][y] = w;
    pre[i][j][l][r][x][y] = {i - 1, j - (r - l + 1), L, R, X, Y};
}

void print(Pre t) 
//从结束状态递归回推整个方案
{
    if (!t.j) return; //从结束状态回推到没选中格子的状态（起始状态）即可结束
    print(pre[t.i][t.j][t.l][t.r][t.x][t.y]); //往回递推
    //输出当前层选中的所有格子
    for (rint i = t.l; i <= t.r; i++) printf("%lld %lld\n", t.i, i);
}

signed main()
{
    cin >> n >> m >> k;
    for (rint i = 1; i <= n; i++)
    {
        for (rint j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            s[i][j] = s[i][j - 1] + a[i][j]; 
        }		
	}
	
    memset(f, -0x3f, sizeof f);
    for (rint i = 0; i <= n; i++) f[i][0][0][0][1][0] = 0;

    for (rint i = 1; i <= n; i++)
      for (rint j = 1; j <= k; j++)
        for (rint l = 1; l <= m; l++)
          for(rint r = l; r <= m; r++)
          {
            if(r - l + 1 > j) break; 
			//当前行选的格子数 > 选中的总格子数，不合法的状态直接跳过

            int w = s[i][r] - s[i][l - 1]; 
			//记录当前行选中 l ~ r 能获得的总价值

            //状态 1 左边界递减，右边界递增（左、右边界都扩张）
            //状态 1.1 j == r - l + 1
            if (j == r - l + 1) 
			{
				f[i][j][l][r][1][0] = w + f[i - 1][0][0][0][1][0]; 
				//f[i - 1][0][0][0][1][0] = 0
			}
            else //状态 1.2 j > r - l + 1
            {
                for (rint p = l; p <= r; p++)
                  for (rint q = p; q <= r; q++)
                    turn(i, j, l, r, 1, 0, p, q, 1, 0, w + f[i - 1][j - (r - l + 1)][p][q][1][0]);
            }

            //状态 2 左边界递减，右边界递减（左边界扩张，右边界收缩）
            for (rint p = l; p <= r; p++)
                for (rint q = r; q <= m; q++)
                {
                    turn(i, j, l, r, 1, 1, p, q, 1, 0, w + f[i - 1][j - (r - l + 1)][p][q][1][0]);
                    turn(i, j, l, r, 1, 1, p, q, 1, 1, w + f[i - 1][j - (r - l + 1)][p][q][1][1]);
                }

            //状态 3 左边界递增，右边界递增（左边界收缩，右边界扩展）
            for (rint p = 1; p <= l; p++)
                for (rint q = l; q <= r; q++)
                {
                    turn(i, j, l, r, 0, 0, p, q, 0, 0, w + f[i - 1][j - (r - l + 1)][p][q][0][0]);
                    turn(i, j, l, r, 0, 0, p, q, 1, 0, w + f[i - 1][j - (r - l + 1)][p][q][1][0]);
                }

            //状态 4 左边界递增，右边界递减（左、右边界都收缩）
            for (rint p = 1; p <= l; p++)
                for (rint q = r; q <= m; q++)
                {
                    turn(i, j, l, r, 0, 1, p, q, 0, 0, w + f[i - 1][j - (r - l + 1)][p][q][0][0]);
                    turn(i, j, l, r, 0, 1, p, q, 0, 1, w + f[i - 1][j - (r - l + 1)][p][q][0][1]);
                    turn(i, j, l, r, 0, 1, p, q, 1, 0, w + f[i - 1][j - (r - l + 1)][p][q][1][0]);
                    turn(i, j, l, r, 0, 1, p, q, 1, 1, w + f[i - 1][j - (r - l + 1)][p][q][1][1]);
                }

                //更新并记录最大价值，以及最大价值对应的状态（结束状态）
                if (j == k) //所有选中 k 个格子的状态都是结束状态
                {
                    for (rint x = 0; x < 2; x++)
                      for (rint y = 0; y < 2; y++)
                        if(res < f[i][k][l][r][x][y])
                        {
							res = f[i][k][l][r][x][y];
							ans = {i, k, l, r, x, y};
						}
                            
                    }
                }

    printf("Oil : %lld\n", res);
    print(ans);

    return 0;
}

AcWing 277. 饼干

贪心的角度出发，贪婪度大的孩子应该获得更多的饼干，才能使整体的怨气总和变得更小，这一点用邻项交换的方法能证明。因此可以降所有孩子按照贪婪值从大到小排序，这样他们分配到的饼干数就是单调递减的。根据这个性质，我们能够更好的维护 \(a[i]\)，即分到的饼干比第 \(i\) 个孩子多的人数，便于我们计算每个孩子的怨气

设 \(f[i][j]\) 表示前 \(i\) 个孩子一共分配了 \(j\) 块饼干时，他们的怨气总和最小值

考虑第 \(i + 1\) 个孩子分到的饼干数量，以此来进行状态转移，转移时共有两种情况。

    1. 第 \(i + 1\) 个孩子获得的饼干数比第 \(i\) 个孩子少，此时由于每个孩子分到的饼干数时递减的，所以前 \(i\) 个孩子分到的饼干数都比第 \(i + 1\) 个孩子多，而后面的所有孩子分到的饼干数量都不会大于第 $i + 1 $ 个孩子，因此此时 \(a[i + 1] = i\)，即有 \(i\) 个人分到的饼干比第 \(i + 1\) 个孩子多。
    1. 第 \(i + 1\) 个孩子获得的饼干数和第 \(i\) 个孩子相同，此时还需要知道 \(i\) 前面有几个孩子与 \(i\) 获得的饼干数也相同，才能计算出 \(a[i + 1]\)

无论是以上哪种情况，我们都需要知道第 \(i\) 个孩子获得的饼干数，以及 \(i\) 前面有多少个孩子与 \(i\) 获得的饼干数相同，但是目前的 \(dp\) 状态难以维护这两个信息。

这里我们不妨对状态做一个等价转换。

    1. 若第 \(i\) 个孩子获得的饼干数大于 \(1\)，则等价于分配 \(j - i\) 个饼干给前 \(i\) 个孩子，即每人少拿一块饼干，这样所有人获得的饼干数之间的相对大小关系没有发生改变，从而怨气总和也不变。
    1. 若第 \(i\) 个孩子获得的饼干数为 \(1\)，由于每个孩子必须有一块饼干，因此不能再减少，这时则需要枚举 \(i\) 前面有多少个孩子也获得 \(1\) 块饼干。

通过这样一个等价转换的方式得出整个算法的状态转移方程：

\[f[i][j] = min(f[i][j-i],\min_{0≤k<i}{\{f[k][j-(i-k)]+k*\sum_{p=k+1}^{i}g[p]\}}) \]

最开始没有分配一个饼干，因此起始状态为 \(f[0][0] = 0\)，结束状态就是将 \(m\) 个饼干分给 \(n\) 个小孩，即 \(f[n][m]\)

这题启发我们可以用额外的算法确定 \(dp\) 状态的计算顺序，还可以在状态空间中运用等效的方法对状态进行缩放，使得需要计算的问题得到非常大的简化，更容易维护和转移。

int n, m;
//g[i] 表示第 i 个小孩的贪婪度
//c[i] 表示贪婪度第 i 大的小孩在原序列中排第 c[i] 个
//s[i] 表示 c[i] 的前缀和
int g[N], c[N], s[N];
int f[N][M]; 
//f[i][j] 表示前 i 个孩子一共分配了 j 块饼干时，他们的怨气总和最小值
pair<int, int> pre[N][M]; 
//pre[i][j] 记录 f[i][j] 的前驱状态
int res[N]; 
//res[i] 表示最优方案中第 i 个孩子分到的饼干数

bool cmp(int a, int b) //比较函数，按照贪婪度从大到小排序
{
    return g[a] > g[b];
}

void print(pair<int, int> t) 
//从结束状态回推整个方案
{
    int a = t.first, b = t.second;
    if (!a) return; 
	//如果回推完每个人的饼干数，结束
    print(pre[a][b]); //从当前状态继续回推方案

    /*
    如果当前状态和前一个状态分糖果的人数相同，说明是 f[i][j] = f[i][j - i]，
    这种情况在转移的过程中我们进行了前 i 个孩子都少一块饼干的等价转换，所以
    回推的时候需要往回转换，即前 i 个孩子增加一块饼干
    */
    if (pre[a][b].first == a) for(rint i = 1; i <= a; i++) res[c[i]]++;
    else
    {
        /*
        否则说明前一个状态到当前状态的中间这段小孩都是相同饼干数，由于递归进
        去再出来，所以这一段在整个序列的最末尾，这一段小孩的饼干数对当前状态
        来说可以取最小，即取 1
        */
        for (rint i = pre[a][b].first + 1; i <= a; i++) res[c[i]] = 1;
    }
}

signed main()
{
    cin >> n >> m;
    for (rint i = 1; i <= n; i++) cin >> g[i];
    for (rint i = 1; i <= n; i++) c[i] = i;
    sort(c + 1, c + 1 + n, cmp); 
    for (rint i = 1; i <= n; i++) s[i] = s[i - 1] + g[c[i]];
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (rint i = 1; i <= n; i++)
    {
        for (rint j = i; j <= m; j++) //每个小孩至少一个饼干，前 i 个小孩至少 i 个饼干
        {
            //状态 1
            f[i][j] = f[i][j - i];
            pre[i][j] = {i, j - i};

            //状态 2
            for (rint k = 0; k < i; k++) 
			//枚举有多少个小孩的饼干数 > 第 i 个小孩
                if(f[i][j] > f[k][j - (i - k)] + (s[i] - s[k]) * k)
				//如果当前状态的怨气总和能更小
                {
                    f[i][j] = f[k][j - (i - k)] + (s[i] - s[k]) * k;
                    pre[i][j] = {k, j - (i - k)};
                }
        }		
	}

    cout << f[n][m] << endl; 
    print({n, m}); 
    for (rint i = 1; i <= n; i++) cout << res[i] << " "; 
    return 0;
}

标签：状态,x1,饼干,int,rint,max,线性,动态,dp
From： https://www.cnblogs.com/spaceswalker/p/18185822

相关文章

  • 【视频】多元线性回归模型原理讲解与R语言实例
    原文链接：https://tecdat.cn/?p=36149原文出处：拓端数据部落公众号分析师：XueYang近年来，随着计量经济学和统计学的快速发展，回归模型作为一种有效的数据分析工具，被广泛应用于金融市场的分析中。回归模型能够通过建立变量之间的数学关系，揭示变量之间的相互作用机制，并预测未来趋势。......
  • mybatisplus 中查询的实体对应的表名是动态的解决方案
    开发中遇到需要查询一些表里的数据，这些数据按照一定的规则存放在不同的数据库表里，例如表名是table_name+月份 table_name_2024_05，table_name_2024_04这样，这些表的结构都相同。网上找了一些动态修改实体对应数据库表名的方法，操作相对复杂而且跟mybatisplus的版本有关。自己......
  • 两个问题类似的dp，二者有时间复杂度的不同
    1.https://vjudge.net/problem/POJ-2229/origin（这个问题是以2的倍数为物品的背包）1#include<iostream>#include<cstdio>#include<fstream>#include<algorithm>#include<cmath>#include<deque>#include<vector>#include<que......
  • keycloak~登录皮肤动态切换的尝试
    keycloak的登录皮肤theme，可以设置领域全局的，或者每个客户端进行单独设置，这种设计是没有问题的，但有时，一个客户端可能有多种主题，这时，你只能再加个客户端，对应新的主题，但这样不方便日后的统计，因为很多统计维度都是以client为基础的，所以，我们需要在进入登录页时，让开发人员转具体的皮肤参......
  • 第 1 节 向量及其线性运算
    第一节向量及其线性运算一、向量的概念向量：既有大小，又有方向的量自由向量：与起点无关的向量向量的大小叫做向量的模.向量\(\vec{AB}\),a和\(\vec{a}\)的模依次记作\(|\vec{AB}|\),|a|和\(|\vec{a}|\).模等于1的向量叫做单位向量.模等于零的向量叫做零向量，记作0......
  • 洛谷题单指南-动态规划3-P1775 石子合并（弱化版）
    原题链接：https://www.luogu.com.cn/problem/P1775题意解读：计算合并石子的最小代价，区间DP。解题思路:状态表示：dp[i][j]表示将第i~j堆石子合并的最小代价，m[i]表示第i堆石子质量，s[i]表示前i堆石子质量前缀和状态转移：考虑最后一次合并，设最后一次合并是将i~k合成的一堆与k+1~j合成......
  • Intel 显卡单机多卡 FSDP 模型 checkpointing 时 Assert Out
    Intel显卡单机多卡FSDP模型checkpointing时AssertOut Intel显卡单机多卡FSDP模型checkpointing时AssertOut现象根因顺藤摸瓜抽丝剥茧解法最后的话现象使用HuggingFaceTrainer在单机多卡环境下对LLAMA2-7B进行LoRAfinetuning时，......
  • Freerdp基本参数说明
    Freerdp基本参数说明语法：xfreerdp[file][options][/v:<server>[:port]] 基础参数： /v:主机IP地址 /u:登录账号 /p:登录密码 /f 全屏显示 /port:3389 端口定义 /version版本查询 /help帮助查询 扩展参数： /bpp:[8/16/24/32] 画面效果和流畅度 /sound:sys:pul......
  • 一道DP(2024ICPC武汉邀请赛A)-shaking trees
    ShakingTrees题外话这题易哥哥跟我说这题的时候，点明了这题是关于高度\(100\)的\(O(n^3)\)或者\(O(n^4)\)的dp，还有提出切割点的概念使序列化。dp是真的，序列化也是真的。只能说易哥哥我的神。不过其实切割点是根据树形态而变的，之前一直以为是不变的，歪了好久。不知道是我没get到......
  • XFreerdp2.x编译安装
    1、下载freerdp编译包gitclonehttps://github.com/FreeRDP/FreeRDP.git或者指定版本zip文件下载 2、安装freerdp所依赖包foriin`find./-typef`;docat${i}|grep-i'openssl-devel';if[$?=="0"];thenecho"${i}";fi;done查看需要的安装包2.x版本的实际......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99