类似题目：https://ac.nowcoder.com/acm/problem/50493 石子位置成一个环(就是多存一遍石子，跑2*n大致题意： 个石子，每个石子有一定的价值，每次可以合并相邻个石子，合并的代价是两个石子的价值和，合并完后两个石子的价值累加一成石子的价值，问将 个石子合并成一个石子的最小代价是多少。分析: 考虑子问题,对于区间 的石子合并成一个石子，更小的子问题就是区间已经分成了两个石子然后合并成一个石子，那么代价其实就是区间所有石子价值和(用前缀和 维护)。假如我们已经得到了 , 的最优合并解，那么对于 的最优解应该是: . 表示当前子问题合并的代价。 那么如何抉择循...

题目大意：给定 种花 个花瓶，每种花插在花瓶上都有一个美观值 ,对于第 种花，满足第 种花插在的花瓶位置一定是在第 种花插在花瓶位置之前.每个花瓶只能插一种花。问将 朵花插入花瓶最大的美观值之和是多少.并且输出插入花瓶的位置方案。(如果有方案美观值相同，按字典序最小输出) 分析：动态规划. 表示第 种花插入第 个花瓶、前 种花插入前 个花瓶的最大美观值。 转移方程： . 可以用前缀和维护。 最优解方案可以用 表示当前 前 种花插入前 个花瓶中可以获得最大的美观值，第 种花插入的花瓶位置。因为是字典序最小所以转移时 就是最大美观值，获得方案，需要倒序遍历找到最优位置，然后倒置输出。 #i...

类似题目：https://ac.nowcoder.com/acm/problem/14701 取数游戏题意： 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * ，其中 表示第 次取数（从1开始编号）。并且每次取走的各个元素只能是该元素所在行的行首或行尾。一共取 次，问每行取数的最大得分和是多少。 分析：每行取数互不影响，所以我们依次计算每行的最大取数方案累加起来即可。 和 的范围不大，我们可以定义 表示该行左边取数取到 位置，右边取数取到 位置的最大得分。进行dfs记忆化搜索答案。 注意数据范围爆long long,用__int128才能过. #include&l...

题意：给定花费上限 ,你有 件物品，有m 件装饰品，每件物品和每件装饰品都有两个值攻击力 和花费 。一个物品最多被一个装饰品所装饰，每个装饰品不能独立存在，问在不超过花费上限的前提下，攻击力最大能到达多少.购买限制：物品最多只能买五个.并且同一种商品不能重复购买. 分析：每种商品只能选购一次，那么就是01背包问题，状态的值就是当前ATK的最大值. 根据数据范围开状态，我们可以让花费作为状态的第一维，题目限制买的物品数量不超过5个，购买物品的数量作为状态的第二维，并且装饰品与物品数量相关，购买装饰品的数量作为第三维。 因为购买装饰品与购买物品唯一相关联的是数量，那么我们可以分两次背包，第一次背...

1.POJ1379 HDU 1109题面相同题意：给定0——X,0——Y的矩形，给定n个点的坐标，在矩形中求得一个点是的该点到所有点的最短距离最大。(保留小数 )分析：模拟退火(随机化)算法，可求解精度要求较小的几何寻点问题.随机选取多个(20个)初始点，进行多次随机坐标变换，并且根据降温概率进行选择是否转移次优解。随机坐标变换：随机半径，随机角度进行改变坐标. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<ctime>...

%参考fyj大佬题解：https://blog.nowcoder.net/n/9eb663297d054e8898236cf06bed7f17分析：骚区间定义：区间左端点为区间的第二小值,区间右端点为区间的第二大值.给定序列是一个1-n的排列,所以无重复元素.求所有骚区间个数.容易想到枚举一个端点，求另外一个端点的有效个数，然后依次累加.原序列定义为 . 对于当前下标为 的元素作为区间左端点 , 是下标大于 并且值小于 的下标最小的元素， 是下标大于 并且值小于 的下标最小元素。那么有效右端点一定是在 中.表示为： 对于当前下标为 的元素作为区间右端点 , 是下标小于 并且值大于...

#Robot Sends Red Packets > https://ac.nowcoder.com/acm/contest/8829/E n个硬币分成若干堆，每堆硬币的价值相同，求最堆最小价值的分配方案。 思路：三层dfs剪枝. #include<bits stdc++.h> using namespace std; typedef long long ll; ll dp[100][2]; int sum=0; int b[100],a[100]; int m; int n; vector<int> gg; bool f; int cnt=0; bo...

1.求01矩阵中最大子正方形的面积.(n<=1e3) https://leetcode-cn.com/problems/maximal-square/ 分析：考虑动态规划。 表示以 为当前最大正方形的右下角时的正方形的最大边长。那么转移方程： #include<bits/stdc++.h> using namespace std; const int maxn=3e3+10; int dp[maxn][maxn],a[maxn][maxn]; int main() { int n,m,ans=0; cin>>n>>m; ...

1.条件类型最短路 https://ac.nowcoder.com/acm/contest/370/B 题意：n个点，m无向边，n个点有一部分是特殊的点，求从1走到n最短路是多少。并且该最短路满足走过的特殊点不超过K.分析: 将所有点的状态分离成K个点(K分层图)，表示到当前该点的走过的特殊点有 个。然后跑一遍dij即可。(dis多建一维条件跑dij也可以) #include<bits/stdc++.h> #define ll long long #define inf 0x7f7f7f7f #define pr pair<ll,ll> using namespa...

大致题意：给定一个序列，求 . 表示 和 十进制下的位数差.分析：方法一:离散+树状数组我们可以逆序遍历序列，计算当前 作为 的左参数的贡献，那么我们与 相加能产生数位差 .举个例子：能至少产生一位数位差，设比 大的最小十进制数位 ，那么 的大小一定要大于等于 .依次枚举至少产生两位数位差.....其实就是遍历所有的十进制数字进行查找.那么当我们求解 的数位差贡献时，必须要有一个数据结构存储 ,并且使其有序才能进行二分查找符合条件的 的个数。-------离散所有可能出现的值(大概9e5)，然后树状数组维护即可. #include<bits/stdc++.h> #define l...

[CQOI2011]动态逆序对

1.费马小定理运算推公式https://ac.nowcoder.com/acm/contest/5945/D

大致题意：一个序列，可以执行两种操作。 对区间 内的元素依次对x取 ，然后将结果赋值给 . 求区间元素和。 分析：这道题跟区间开方思路类似。每次对一个区间进行gcd的话一般会有大部分会变成1，可以用一些小技巧来保证复杂度不会太差，用一个tag变量去标记一下这个区间是不是全都相等，再用一个sam变量去标记区间全相等的时候的元素大小，这样修改的时候对于区间元素都相等的直接对sam进行gcd即可。最后用一个线段树维护标记。(虽然区间开方的题目我是用分块,不过线段树还是挺好写的 #include<bits/stdc++.h> #define ls cur<<1 ...

规律题，挂一个暴力打表的代码。 #include<bits/stdc++.h> using namespace std; int a[1005]; int n; int vis[2005],b[1005]; int ans; void dfs( int x,int y ) { if( x>n ) { if( y==2*n ) { ans++; for( int i=1;i<=n;i++ ) printf("%d ",a[i]); p...