你肯定以為DP專練會(huì)有很多題，

但是請考慮一下本仙女的DP碼力，一次性能更幾個(gè)題。。。

來吧，別害怕呀~~

文章目錄

• 大理石
• • 題目
  • 題解
  • 代碼實(shí)現(xiàn)
• 數(shù)字計(jì)數(shù)
• • 題目
  • 題解
  • 代碼實(shí)現(xiàn)

大理石

題目

林老師是一位大理石收藏家，他在家里收藏了n塊各種顏色的大理石，第i塊大理石的顏色為ai。但是林老師覺得這些石頭在家里隨意擺放太過凌亂，他希望把所有顏色相同的石頭放在一起。換句話說，林老師需要對現(xiàn)有的大理石重新進(jìn)行排列，在重新排列之后，對于每一個(gè)顏色j，如果最左邊的顏色為j的大理石是第l塊大理石，最右邊的顏色為j的大理石是第r塊大理石，那么從第l塊大理石到第r塊大理石，這些石頭的顏色都為j。

由于這些大理石都比較重，林老師無法承受這些大理石的重量太久，所以他每次搬運(yùn)只能交換相鄰的兩塊大理石。請問，林老師最少需要進(jìn)行多少次搬運(yùn)？

輸入格式
第一行輸入一個(gè)數(shù)字n（2≤n≤4*10^5），表示大理石的總數(shù)。
第二行輸入n個(gè)數(shù)字a1，a2…,an（1≤ai≤20）表示第i塊大理石的顏色為ai。
輸出格式
輸出林老師最少需要搬運(yùn)的次數(shù)。

樣例
樣例輸入 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

題解

剛上來就這么猛滴嗎！！！
我們從數(shù)據(jù)范圍入手，看看n的范圍，嘖嘖嘖
明顯不想讓我們用暴力兩兩交換，O(N²)必定炸嗨，對此我只想說↓

再觀察顏色1~20，是不是太小了，這在暗示我們什么，是什么！！
狀壓DP啊，wahahahaah→瘋子

進(jìn)入正解
搞成二進(jìn)制，i位如果為1表示這個(gè)顏色已經(jīng)被我們堆成一堆
反之則仍需處理

首先應(yīng)該明白，假設(shè)i在j左邊，
把i往右移到j(luò)右邊，其實(shí)相當(dāng)于把j左移
所以為了方便我們就統(tǒng)一方向，向左看（口令）~~←

本大大是枚舉情況i，如果j位上面是1，
我就找到上一次狀態(tài)pre，即j還未被堆在一起的狀態(tài)
見代碼?

if ( i & ( 1 << j ) )
pre = i - ( 1 << j )

那么DP就出來了：
$dp[i]=min(dp[i],dp[pre]+cost)$

其實(shí)這道題的難點(diǎn)就是如何突破這個(gè)cost
突破了就直接狀壓板子走一遭，路迢迢
我們直接統(tǒng)計(jì)i，j表示i，j兩種顏色，現(xiàn)在要將j顏色移動(dòng)到i顏色前面
cost[i][j]其實(shí)就要加上對于每一個(gè)j顏色石頭所在的位置前面有多少個(gè)顏色i的石頭
因?yàn)槊恳粋€(gè)j都要與它前面的每一個(gè)i交換，彼此路過，擦肩而過后的心動(dòng)，好浪漫

其實(shí)剛開始我也在思考為什么是顏色個(gè)數(shù)，
而不是找到i，j位置然后加上（j-i+1）的距離

后來我想懂了，因?yàn)槭莾蓛删o緊挨著交換，
如果存在一個(gè)顏色i，另一個(gè)顏色j的兩個(gè)石頭，中間有其他亂入棒打鴛鴦 的顏色
那么我們也會(huì)用cost計(jì)算出i，k和j，k交換的個(gè)數(shù)，
然后再這之前又會(huì)計(jì)算出i，l和l，k直到兩個(gè)石頭是緊密相連，心心相通為止
而將這些相加其實(shí)就剛好是答案

代碼實(shí)現(xiàn)

#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; }

數(shù)字計(jì)數(shù)

題目

給定兩個(gè)正整數(shù)a 和 b，求在 [a,b] 中的所有整數(shù)中，每個(gè)數(shù)碼 (digit) 各出現(xiàn)了多少次。

輸入格式
僅包含一行兩個(gè)整數(shù)a,b ，含義如上所述。
輸出格式
包含一行 10個(gè)整數(shù)，分別表示 0~9 在[a,b] 中出現(xiàn)了多少次。

樣例
樣例輸入
1 99
樣例輸出
9 20 20 20 20 20 20 20 20 20
數(shù)據(jù)范圍與提示
30% 的數(shù)據(jù)中，1≤a≤b≤10⁶；
100%的數(shù)據(jù)中，1≤a≤b≤10¹²。

題解

WOO！這道題，不得了，不得了，給俺整瘋了！
話不多說，這道題求[a,b]一般這種區(qū)間題，我們都要用到一點(diǎn)點(diǎn)差分思想
將其轉(zhuǎn)化為$[1,b]?[1,a?1]$
我們先算出所有的情況個(gè)數(shù)，包含前導(dǎo)零，后面我們再來?前導(dǎo)零
設(shè)dp[i][j][k]表示位數(shù)為i時(shí)以j開頭的值為k的個(gè)數(shù)
$dp[i][j][k]=dp[i][j][k]+dp[i?1][j][k]$$(j!=k)$
$dp[i][j][k]=dp[i][j][k]+dp[i?1][j][k]+pow(10,i?1))$$(j==k)$
為什么要加上10^i-1，
簡單解釋：當(dāng)以j開頭的時(shí)候后面一共有10^i-1種情況，這個(gè)時(shí)候j都作為最高位+1

最后就開始統(tǒng)計(jì)即可
1)統(tǒng)計(jì)出位數(shù)從1——最高位數(shù)len-1，這些都是滿足的，
但是注意這些情況的統(tǒng)計(jì)都不能以0作為最高位，排除掉前導(dǎo)零
2）統(tǒng)計(jì)出位數(shù)為len，從1——len位數(shù)上的值digit[len]-1，這些也是滿足的，
注意這個(gè)時(shí)候的統(tǒng)計(jì)，第二重循環(huán)j就可以以0開頭，反正前面有l(wèi)en的值給我們撐腰
3）接著就是將2）情況以此類推，對于位數(shù)為i的，
固定從1——i位數(shù)上的值digit[i]-1,然后加上后面所有的0~9符合情況的個(gè)數(shù)
最后再說一個(gè)注意點(diǎn)：后面代碼的取模操作，舉例說明：
1234，固定1，就是234，1的出現(xiàn)次數(shù)要加上234+1，
即統(tǒng)計(jì)了1000~1234中的最高位1出現(xiàn)次數(shù)

好了，看代碼吧，我口胡不行了。。。

代碼實(shí)現(xiàn)

#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; }

好了，我已經(jīng)彈盡糧絕了，撤了

總結(jié)

以上是生活随笔為你收集整理的DP专练2 （大理石 + [ZJOI 2010]数字计数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。