记念化寻觅

2019-09-23 作者:每日影评   |   浏览(138)

      很感动,有这么一个国度,走过了很多弯路,同时也在不断改进中前进,消除冷漠,消除歧视,we are family,we are friends

题目链接:

Ember是一个雄心勃勃的Web应用程序,消除了样板,并提供了一个标准的应用程序架构的JavaScript框架。

  

Ember.js 1.0 RC3 发布了,比起 RC2 版本,RC3 在性能又进一步提升,同时还包含如下改进:

题目描述:

  • When adjacent child views are scheduled for insertion they are are now batched together, and inserted together rather then one at a time.
  • Object deletion is now async, this prevents un-needed churn when destroying large interconnected object graphs.
  • The number of objects allocated during view rendering has been cut down.

Blocks

示例代码:

 

view sourceprint?

王中王全年开奖码,Description

01 MyApp.president = Ember.Object.create({

Some of you may have played a game called 'Blocks'. There are n blocks in a row, each box has a color. Here is an example: Gold, Silver, Silver, Silver, Silver, Bronze, Bronze, Bronze, Gold. 
The corresponding picture will be as shown below: 

02   firstName: "Barack",

王中王全年开奖码 1 
王中王开奖一马中特,Figure 1

03   lastName: "Obama",

If some adjacent boxes are all of the same color, and both the box to its left(if it exists) and its right(if it exists) are of some other color, we call it a 'box segment'. There are 4 box segments. That is: gold, silver, bronze, gold. There are 1, 4, 3, 1 box(es) in the segments respectively. 

04  

Every time, you can click a box, then the whole segment containing that box DISAPPEARS. If that segment is composed of k boxes, you will get k*王中王救世网,k points. for example, if you click on a silver box, the silver segment disappears, you got 4*4=16 points. 

05   fullName: function() {

Now let's look at the picture below: 

06     return this.get('firstName') + ' ' + this.get('lastName');

王中王全年开奖码 2 
Figure 2

07  

The first one is OPTIMAL. 

08   // Tell Ember that this computed property depends on firstName

Find the highest score you can get, given an initial state of this game. 

09   // and lastName

Input

10   }.property('firstName', 'lastName')

The first line contains the number of tests t(1<=t<=15). Each case contains two lines. The first line contains an integer n(1<=n<=200), the number of boxes. The second line contains n integers, representing the colors of each box. The integers are in the range 1~n.

11 });

Output

For each test case, print the case number and the highest possible score.

Sample Input

2
9
1 2 2 2 2 3 3 3 1
1
1

Sample Output

Case 1: 29
Case 2: 1

题目大意:

  同种颜色的块块可以消除,每次得分是数量的平方,求最大得分

思路:

  一看是个dp题目

  先缩点,记录 color 和 len, 设计状态 dp[ i ][ j ][ k ] 表示第 i 到 j 段的最大得分,其中第 j 段和从右边过来的 k 个长度的同种颜色一起消除了

  保证 j 和 k 之间在之前被消除

  状态转移方程为

  dp[l][r][k] =

    max( dp[ l ][ r - 1 ][ 0 ] + (k + len[r])*(k + len[r]), max{ dp[ l ][ i ][ len[r] + k ] + dp[ i + 1 ][ r - 1 ][ 0 ] } )

  其中 r > i >= L 

  然后记忆化搜索即可 

代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int N = 210;
 8 
 9 int n, c[N], len[N], dp[N][N][N];
10 
11 int solve(int l, int r, int k) {
12     if (dp[l][r][k])return dp[l][r][k];
13     if (l == r)return dp[l][r][k] = (len[r] + k)*(len[r] + k);
14     dp[l][r][k] = solve(l, r - 1, 0) + (k + len[r])*(k + len[r]);
15     for (int i = l; i < r; ++i)if (c[i] == c[r])
16         dp[l][r][k] = max(dp[l][r][k], solve(l, i, len[r] + k) + solve(i + 1, r - 1, 0));
17     return dp[l][r][k];
18 }
19 
20 int main() {
21     int t, ca = 0;
22     scanf("%d", &t);
23     while (t--) {
24         memset(dp, 0, sizeof(dp));
25         scanf("%d", &n);
26         int a[N];
27         for (int i = 0; i < n; ++i)
28             scanf("%d", &a[i]);
29         int q = 0;
30         for (int i = 0; i < n; ++i) {
31             if (i&&a[i] == a[i - 1])++len[q];
32             else c[++q] = a[i], len[q] = 1;
33         }
34         printf("Case %d: %dn", ++ca, solve(1, q, 0));
35     }
36 }

 

本文由王中王救世网发布于每日影评,转载请注明出处:记念化寻觅

关键词:

  • 上一篇:没有了
  • 下一篇:没有了