Topic link

【 The valley gate 】

Answer key

\(f[i][j][k]\) It means to eliminate \((i,j)\), Add... To the back \(k\) The total number of beads per bead .
Consider three kinds of decisions :( The title gives \(k\) It is expressed as \(K\))

Decision making 1

When \(k<K-1\) when , Consider adding a bead , That is the state \(f[i][j][k+1]\) Transfer to get \(f[i][j][k]\). Because with a bead , So the equation is \(f[i][j][k]=min(f[i][j][k+1]+1)\)

Decision making 2

If \(k=K+1\), It shows that this can be eliminated , That is from \(f[i][j][k]=f[i+1][j][0]\).

Decision making 3

If \(i\) The color and \(i+1\) It's the same color , So you can take \(i\) Add to \(i+1\) in , So the equation is \(f[i][j][k]=f[i+1][j][k+1]\).

The answer is obviously \(f[1][n][0]\).


In view of this problem, the equation and the state transfer between the equations are relatively scattered , So it's easy to use memory search .

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 105
using namespace std;
int f[N][N][N], a[N];
int n, K;
int DP(int l, int r, int k) {
if (f[l][r][k] != -1) return f[l][r][k];
if (l > r) return 0;
f[l][r][k] = inf;
if (k < K - 1) f[l][r][k] = min(f[l][r][k], DP(l, r, k + 1) + 1);
if (k == K - 1) f[l][r][k] = DP(l + 1, r, 0);
for (int i = l + 1; i <= r; i ++)
if (a[i] == a[l]) f[l][r][k] = min(f[l][r][k], DP(l + 1, i - 1, 0) + DP(i, r, min(K - 1, k + 1)));
return f[l][r][k];
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> K;
for (int i = 1; i <= n; i ++) cin >> a[i];
memset(f, -1, sizeof(f));
DP(1, n, 0);
cout<< f[1][n][0] << endl;
return 0;
}

「SPOJ6340」「BZOJ1939」ZUMA - ZUMA【 Memory search 】 More articles about

  1. LG2530 「SHOI2001」 Packing man in chemical plant High dimensional DP+ Memory search

    Problem description LG2530 Answer key set up \(opt[i][a][b][c][d]\) It's for the third time \(i\) After a , The first \(1,2,3\) There are still \(a,b,c\) The minimum number of operands . Memory search . Revelation : What if ...

  2. Codeforces Round #336 (Div. 2) D. Zuma Memory search

    D. Zuma Topic linking : http://www.codeforces.com/contest/608/problem/D Description Genos recently installed t ...

  3. 【CF607B】Zuma—— Section dp( Memory search / Recurrence )

    The following is a translation from Chinese into Mandarin : Given a length less than or equal to 500 Sequence , Each number represents a color , One palindrome string can be deleted at a time , Ask how many times you can cancel at most ? (7.16) This question starts from Luogu pend When I came back, it showed that 103 A test point ( ...

  4. 「kuangbin Take you fly 」 Topic 22 Section DP

    layout: post title: 「kuangbin Take you fly 」 Topic 22 Section DP author: "luowentaoaa" catalog: true tags: - ku ...

  5. 「kuangbin Take you fly 」 Topic 12 Basics DP

    layout: post title: 「kuangbin Take you fly 」 Topic 12 Basics DP author: "luowentaoaa" catalog: true tags: mathj ...

  6. Peace of all 「 Enjoy e raw 」 If it's really awesome ?

    In recent days, , With the Internet gene . Big losers ( It's been three years since it was founded. It's basically unprofitable , The loss at the end of the second quarter of this year was nearly 4 Billion , You can count on how powerful it is ?). Property insurance company — Zhongan launched “ Enjoy e raw ” Medium and high end medical insurance ( Property insurance companies are really good at operating high-end medical services ? It's really high-end medical insurance ...

  7. XCActionBar 「Xcode Medium Alfred」

    Download address :https://github.com/pdcgomes/XCActionBar Basic commands : (1)「command+shift+8」 Or double click 「command」 Key can open 「 Action input box window 」 ( ...

  8. Git perform 「fork Out of the warehouse 」 and 「 The latest version of the original warehouse 」 Content synchronization update

    When we're in GitHub On fork Out of a warehouse , If the original warehouse is updated , How can we ensure that we fork The content of the warehouse is the same as that of the original warehouse ? We generally focus on the warehouse  master( Main branches ) The content of , Go through the following steps ...

  9. 【 translate 】 Nishikawa's 「 The game graphics made by the experiment 」「GUILTY GEAR Xrd -SIGN-」 Implemented in 「 Real time of pure cartoon animation 3D graphics 」 The secret of , Later chapters

    http://www.4gamer.net/games/216/G021678/20140714079/     Serial No 2 Back this time ,  Arc System Works Development of the fighting game 「GUILTY G ...

Random recommendation

  1. jQuery Colorbox Summary of the course of using pop-up plug-ins 、 Property settings

    jQuery Colorbox It's a pop-up layer , Content playback plug-in , Excellent results , Of course, I mainly use it to pop up pictures . jQuery Colorbox It's not just elastic animation , Fade in / out effect , Slide show , Width custom , Can also be ajax ...

  2. The operation has always been ul The elements of

    1 $(function() { var all = $(".test"); $(".test").each(function() { var y = $(th ...

  3. Inventory of domestic programmers are not commonly used hot iOS Third party Library : After watching , How dare you call yourself ” Master iOS Development ” Do you ?【 Reprint 】

    comprehensive github The degree of attention and specific use of each project on the website , Covering functions ,UI, database , automated testing , Programming tools, etc , After watching , How dare you call yourself ” Master iOS Development ” Do you ? https://github.com/syedhali/EZ ...

  4. paip.2013 Technology trends and hot spots in 2007 v3.0 cao

    paip.2013 Technology trends and hot spots in 2007 v3.0 cao author Attilax   Elon ,  EMAIL:1466519819@qq.com  source :attilax The column Address :http://blog.cs ...

  5. ionic Project notes

    Recently the company is using ionic do MicroStation , It's hard to avoid some problems in the project . Summarized below : 1.       Changed Slidebox When dynamically binding pictures , The page will show a blank , When changing the window size , The picture comes out , When dynamically binding pictures , ...

  6. POJ 3187 Yang hui triangle + Enumerate permutations Good question

    If we give a formula by 1~n The sequence of components , We can do it every day 2 Sum the numbers , Get a new sequence , Keep repeating , Finally, we get a number sum, Now the input n,sum, It is required to output such an arrangement , If there are multiple situations , Output the one with the smallest dictionary order . Just opened ...

  7. wpf viewmodel Communication between

    Use Prism The third party framework implements ViewModel Communication between Create a class that inherits from UnityBootstrapper public class Bootstrapper : UnityBootstrapper { ...

  8. How to use node Medium buffer

    Introduce :Buffer Class is a global class , It's a rare one that doesn't need require( ‘buffer’ ) You can use the class ,Buffer It's similar to arrays length, The elements in it are 16 The two digits of the base , namely 0-255 Number of numbers ...

  9. Pop up ads at the bottom of the page (css)

    Some single page need to add ads and so on div. Part of the code : <div class="flex"> Content .... </div> The main css Code : .flex{posit ...

  10. qt Drag and drop Change the size ( Two )

    Recent projects need to be implemented windows The effect of a rubber band , So I learned something about it , I wish to record . First windows The system supports rubber band effect , Need to use win32 Fang Law :SystemParametersInfo(SPI_S ...