首页 > 其他分享 >洛谷P9541 「AWOI Round 2 D」数字三角形 题解

洛谷P9541 「AWOI Round 2 D」数字三角形 题解

时间:2024-08-13 22:07:12浏览次数:11  
标签:洛谷 min int 题解 sum P9541 Max magic dp

Problem

Solution

通过题目意思发现,有三种情况:

  1. 没有旋转的初始情况

  2. 旋转一次的情况

  3. 旋转两次的情况

我们考虑怎么处理初始情况,其他情况同理。

首先,我们发现经过数和最大一定可以保证是每行的最大值的总和,所以只要计算最小的消耗就可以了。

考虑 DP,设 \(dp_{i,j}\) 表示从上往下走到 \(i,j\) 时使每行都取最大值时的最小消耗。

容易想到如果当前的数就是当前行的最大值,便可以直接从 \(dp_{i-1,j-1}\) 和 \(dp_{i-1,j}\) 转移过来;如果不是,则只需再加 \(1\) 即可(因为可以调换任意两个数的位置)。

每行的最大值预处理或者动规时处理均可。

注意边界和初始值。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i>=(b);i--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define elif else if
// #define int long long

const int N=1e3+4,INF=INT_MAX;
int n,a[N][N],b[N][N],Maxsum,Minmagic,Max[N],dp[N][N];
void work(int sum,int magic)
{
	For(i,1,n)Max[i]=0;
	For(i,1,n)For(j,1,i)dp[i][j]=INF,Max[i]=max(Max[i],a[i][j]);
	For(i,1,n)sum+=Max[i];
	For(i,1,n)
		For(j,1,i)
			if(a[i][j]==Max[i])dp[i][j]=min(dp[i][j],min(dp[i-1][max(1,j-1)],dp[i-1][min(i-1,j)]));
				else dp[i][j]=min(dp[i][j],min(dp[i-1][max(1,j-1)],dp[i-1][min(i-1,j)])+1);
	int Min=INF;
	For(i,1,n)Min=min(Min,dp[n][i]);
	magic+=Min;
	if(sum>Maxsum)Maxsum=sum,Minmagic=magic;
		elif(sum==Maxsum)Minmagic=min(Minmagic,magic);
}
signed main()
{
	IOS;
	cin>>n;
	For(i,1,n)For(j,1,i)cin>>a[i][j];
	work(0,0);
	For(i,1,n)For(j,1,i)b[i][j]=a[i][j];
	For(i,1,n)For(j,1,i)a[i][j]=b[n+1-j][i-j+1];
	// For(i,1,n){For(j,1,i)cout<<a[i][j]<<" ";cout<<"\n";}
	work(0,n);
	For(i,1,n)For(j,1,i)b[i][j]=a[i][j];
	For(i,1,n)For(j,1,i)a[i][j]=b[n+1-j][i-j+1];
	// For(i,1,n){For(j,1,i)cout<<a[i][j]<<" ";cout<<"\n";}
	work(0,2*n);
	cout<<Maxsum<<" "<<Minmagic;

	return 0;
}

标签:洛谷,min,int,题解,sum,P9541,Max,magic,dp
From: https://www.cnblogs.com/Wu-ZH/p/18357791

相关文章

  • 洛谷-P1250 种树
    Abstract传送门Idea显然是一个差分约束系统。不妨用dist[i]表示前i个位置种的树的数目,那么,容易得出下列方程:dist[i]>=dist[i-1]dist[i]-dist[i-1]<=1(每个位置至多能种一颗树)题目要求b到e之间至少种t棵树,其数学形式就是:dist[b]-dist[e-1]>=t依据......
  • CF895B XK Segments 题解 二分
    题目链接:https://codeforces.com/problemset/problem/895/B题目大意给你一个长度为\(n\)的数列\(a_1,a_2,\ldots,a_n\)。求数列中存在多少个不同的下标对\((i,j)\)满足如下条件:\(a_i\lea_j\)并且恰好有\(k\)个整数\(y\)满足\(a_i\ley\lea_j\)且\(y\)......
  • 题解:CF1957A Stickogon
    原地址:这里思路首先看样例41121162233339422224244首先可以肯定当\(t\)为\(1\)和\(2\)时不能组成多边形,易知要组成最多的多边形,三角形更有性价比,观察样例\(t\)为\(6\)可以发现,只要用相同的木棍除以\(3\)取整便是答案,可能会有人问了,那我用......
  • 题解:AT_abc352_c [ABC352C] Standing On The Shoulders
    原地址:这里大意几个吃饱了撑的巨人在玩叠罗汉,每个人踩在前一个人的肩膀上,求这个叠罗汉最高有多高。思路直接先求出所有巨人的肩高之和,然后再一个一个枚举看加上哪一个巨人的头高最大就行了。代码#include<iostream>usingnamespacestd;inta[200005],b[200005];intmain......
  • 题解:CF1971B Different String
    原地址:这里题意给出字符串\(s\),询问更改\(s\)的排列顺序后与原来的\(s\)是否不同,不同输出YES,否则输出NO。思路只要判断字符串中含有不同的字符即可。代码#include<iostream>#include<cstdio>usingnamespacestd;intmain(){ intt; scanf("%d",&t); while(t-......
  • 洛谷P2758编辑距离超详注解
    注:本蒟蒻第一篇题解本文亦发表于洛谷博客题目跳转题目大意用最少的字符操作次数,将字符串A转换为字符串B。字符操作为:1.删除一个字符;2.插入一个字符;3.将一个字符改为另一个字符。代码思路本题很明显用的是DP1.赋值将dp数组的值赋值到最大2.特殊赋值对......
  • 【题解】 [NOIP 2002 普及组] 产生数
    题目描述题目大意给定\(k\)个规则,规则为“使一位数可变换成另一个一位数”。求整数\(n\)根据规则经过若干次(可以为0次或多次)变化,能生成的整数个数。思路该题主要考察:Floyd传递闭包,高精度乘法。显而易见,规则具有传递性。举个例子,1可变换成2,2可变换成3,则1可变换成3。当然......
  • P8997 题解
    P8997思路按题意模拟,用栈建出二叉树,叶子节点是要填的值,非叶子是运算符。判断一个叶子能贡献能填哪些数并最终成为答案,即dp计算要使该叶子的值\(ans\)成为答案最少要填\(num0\)个\(<=ans\)和\(num1\)个\(>ans\)的数。发现dp只与\(\leans\)和\(>ans\)的数的个......
  • P8996 题解
    P8996思路当有\(a_i<a_j\)时,先放\(a_i\),再放\(i\)之后连续的\(a_k<a_i\)。设\(i\)后第一个比\(a_i\)大的位置是\(nxt_i\),对于一个前缀最大值位置\(i\),合并后\([i,nxt_i)\)的顺序不变且依然连续。让前缀最大值\(a_l\)代表整个区间,可以看做合并是将两个序列的前缀......
  • arc182c 题解
    arc182c思路有\(6\)个小于\(14\)的质数,设这\(6\)个质数的指数分别为\(x_1,\dotsb,x_6\)。\(ans=\sum(\prod_{i=1}^d(x_i+1))\)。状压这\(6\)个数,维护\(val_s=\prod_{i=1}^6(x_i\times[s二进制第i位为1]+[s二进制第i位为0])\)。当加入一个数时,某些\(x_i\)会加......