建设部网站2015年第158号,中国建筑材料网官网,帝国cms建站系统,在家做兼职官方网站平台你肯定以为DP专练会有很多题#xff0c; 但是请考虑一下本仙女的DP码力#xff0c;一次性能更几个题。。。 来吧#xff0c;别害怕呀~~ 文章目录大理石题目题解代码实现数字计数题目题解代码实现大理石
题目
林老师是一位大理石收藏家#xff0c;他在家里收藏了n块各种…你肯定以为DP专练会有很多题 但是请考虑一下本仙女的DP码力一次性能更几个题。。。 来吧别害怕呀~~
文章目录大理石题目题解代码实现数字计数题目题解代码实现大理石
题目
林老师是一位大理石收藏家他在家里收藏了n块各种颜色的大理石第i块大理石的颜色为ai。但是林老师觉得这些石头在家里随意摆放太过凌乱他希望把所有颜色相同的石头放在一起。换句话说林老师需要对现有的大理石重新进行排列在重新排列之后对于每一个颜色j如果最左边的颜色为j的大理石是第l块大理石最右边的颜色为j的大理石是第r块大理石那么从第l块大理石到第r块大理石这些石头的颜色都为j。
由于这些大理石都比较重林老师无法承受这些大理石的重量太久所以他每次搬运只能交换相邻的两块大理石。请问林老师最少需要进行多少次搬运
输入格式 第一行输入一个数字n2≤n≤4*10^5表示大理石的总数。 第二行输入n个数字a1a2…,an1≤ai≤20表示第i块大理石的颜色为ai。 输出格式 输出林老师最少需要搬运的次数。
样例 样例输入 1 7 3 4 2 3 4 2 2 样例输出 1 3 样例输入 2 5 20 1 14 10 2 样例输出 2 0 样例输入 3 13 5 5 4 4 3 5 7 6 5 4 4 6 5 样例输出 3 21
题解 刚上来就这么猛滴吗 我们从数据范围入手看看n的范围啧啧啧 明显不想让我们用暴力两两交换O(N2)必定炸嗨对此我只想说↓ 再观察颜色1~20是不是太小了这在暗示我们什么是什么 状压DP啊wahahahaah→疯子
进入正解 搞成二进制i位如果为1表示这个颜色已经被我们堆成一堆 反之则仍需处理
首先应该明白假设i在j左边 把i往右移到j右边其实相当于把j左移 所以为了方便我们就统一方向向左看口令~~←
本大大是枚举情况i如果j位上面是1 我就找到上一次状态pre即j还未被堆在一起的状态 见代码? if ( i ( 1 j ) ) pre i - ( 1 j ) 那么DP就出来了 dp[i]min(dp[i],dp[pre]cost)dp[i]min(dp[i],dp[pre] cost)dp[i]min(dp[i],dp[pre]cost)
其实这道题的难点就是如何突破这个cost 突破了就直接状压板子走一遭路迢迢 我们直接统计ij表示ij两种颜色现在要将j颜色移动到i颜色前面 cost[i][j]其实就要加上对于每一个j颜色石头所在的位置前面有多少个颜色i的石头 因为每一个j都要与它前面的每一个i交换彼此路过擦肩而过后的心动好浪漫
其实刚开始我也在思考为什么是颜色个数 而不是找到ij位置然后加上j-i1的距离
后来我想懂了因为是两两紧紧挨着交换 如果存在一个颜色i另一个颜色j的两个石头中间有其他乱入棒打鸳鸯 的颜色 那么我们也会用cost计算出ik和jk交换的个数 然后再这之前又会计算出il和lk直到两个石头是紧密相连心心相通为止 而将这些相加其实就刚好是答案
代码实现
#include cstdio
#include cstring
#include iostream
using namespace std;
#define LL long long
#define MAXN 400005
#define COLOR 21
int n, Max;
int a[MAXN], tot[COLOR];
LL cost[COLOR][COLOR], dp[1 COLOR];
int main() {scanf ( %lld, n );for ( int i 1;i n;i ) {scanf ( %d, a[i] );Max max ( Max, a[i] );-- a[i];}for ( int i 1;i n;i ) {tot[a[i]] ;for ( int j 0;j Max;j )cost[j][a[i]] tot[j];}for ( int i 1;i ( 1 Max );i )dp[i] ( 1ll 60 );dp[0] 0;for ( int i 0;i ( 1 Max );i )for ( int j 0;j Max;j )if ( i ( 1 j ) ) {LL val 0;int pre i - ( 1 j );for ( int k 0;k Max;k )if ( pre ( 1 k ) )val cost[j][k];dp[i] min ( dp[i], dp[pre] val );}printf ( %lld, dp[( 1 Max ) - 1] );return 0;
}数字计数
题目
给定两个正整数a 和 b求在 [a,b] 中的所有整数中每个数码 (digit) 各出现了多少次。
输入格式 仅包含一行两个整数a,b 含义如上所述。 输出格式 包含一行 10个整数分别表示 0~9 在[a,b] 中出现了多少次。
样例 样例输入 1 99 样例输出 9 20 20 20 20 20 20 20 20 20 数据范围与提示 30% 的数据中1≤a≤b≤106 100%的数据中1≤a≤b≤1012。
题解 WOO这道题不得了不得了给俺整疯了 话不多说这道题求[a,b]一般这种区间题我们都要用到一点点差分思想 将其转化为[1,b]−[1,a−1][1,b] - [1,a-1][1,b]−[1,a−1] 我们先算出所有的情况个数包含前导零后面我们再来✂前导零 设dp[i][j][k]表示位数为i时以j开头的值为k的个数 dp[i][j][k]dp[i][j][k]dp[i−1][j][k]dp[i][j][k]dp[i][j][k]dp[i-1][j][k]dp[i][j][k]dp[i][j][k]dp[i−1][j][k](j!k)(j!k)(j!k) dp[i][j][k]dp[i][j][k]dp[i−1][j][k]pow(10,i−1))dp[i][j][k]dp[i][j][k]dp[i-1][j][k]pow(10,i-1))dp[i][j][k]dp[i][j][k]dp[i−1][j][k]pow(10,i−1))(jk)(jk)(jk) 为什么要加上10i-1 简单解释当以j开头的时候后面一共有10i-1种情况这个时候j都作为最高位1
最后就开始统计即可 1)统计出位数从1——最高位数len-1这些都是满足的 但是注意这些情况的统计都不能以0作为最高位排除掉前导零 2统计出位数为len从1——len位数上的值digit[len]-1这些也是满足的 注意这个时候的统计第二重循环j就可以以0开头反正前面有len的值给我们撑腰 3接着就是将2情况以此类推对于位数为i的 固定从1——i位数上的值digit[i]-1,然后加上后面所有的0~9符合情况的个数 最后再说一个注意点后面代码的取模操作举例说明 1234固定1就是2341的出现次数要加上2341 即统计了1000~1234中的最高位1出现次数
好了看代码吧我口胡不行了。。。
代码实现
#include cstdio
#include cmath
using namespace std;
#define LL long long
#define MAXN 15
LL a, b;
LL dp[MAXN][MAXN][MAXN];
LL ans[MAXN];
int digit1[MAXN], digit2[MAXN];
int main () {scanf ( %lld %lld, a, b );-- a;int num1 0, num2 0;LL t a;while ( t ) {digit1[ num1] t % 10;t / 10;}t b;while ( t ) {digit2[ num2] t % 10;t / 10;}for ( int i 1;i num2;i )for ( int j 0;j 9;j )for ( int k 0;k 9;k ) {for ( int Q 0;Q 9;Q )dp[i][j][k] dp[i - 1][Q][k];if ( j k ) dp[i][j][k] ( LL ) pow ( 10, i - 1 );}if ( a ) { for ( int i 1;i num1;i )//所有小于num1长度的i,肯定不能以0开头 for ( int j 1;j 9;j )for ( int k 0;k 9;k )ans[k] - dp[i][j][k];for ( int j 1;j digit1[num1];j )for ( int k 0;k 9;k )ans[k] - dp[num1][j][k];a % ( LL ) pow ( 10, num1 - 1 );ans[digit1[num1]] - ( a 1 );for ( int i num1 - 1;i 0;i -- ) {for ( int j 0;j digit1[i];j )for ( int k 0;k 9;k )ans[k] - dp[i][j][k];a % ( LL ) pow ( 10, i - 1 );ans[digit1[i]] - ( a 1 );}}if ( b ) {for ( int i 1;i num2;i )for ( int j 1;j 9;j )for ( int k 0;k 9;k )ans[k] dp[i][j][k];for ( int j 1;j digit2[num2];j )for ( int k 0;k 9;k )ans[k] dp[num2][j][k];b % ( LL ) pow ( 10, num2 - 1 );ans[digit2[num2]] ( b 1 );for ( int i num2 - 1;i 0;i -- ) {for ( int j 0;j digit2[i];j )for ( int k 0;k 9;k )ans[k] dp[i][j][k];b % ( LL ) pow ( 10, i - 1 );ans[digit2[i]] ( b 1 );}}for ( int i 0;i 9;i )printf ( %lld , ans[i] );return 0;
} 好了我已经弹尽粮绝了撤了
