USACO16OPEN 248

题目传送门

比较坑的区间\(DP\)



定义f[i][j]为将i~j这段区间全都合并为一个数的最大值

于是我很自然的就想到了这样转移:

f[i][j] = max(f[i][j], max(f[i][k], f[k+1][j]));
if(f[i][k] == f[k+1][j]) f[i][j] = max(f[i][j], f[i][k] + 1);

但是,因为f[i][k]f[k+1][j]的最大值可能并不相邻,所以第一个转移是不对的,应该只有

if(f[i][k] == f[k+1][j]) f[i][j] = max(f[i][j], f[i][k] + 1);

这样就可以把这道题\(A\)掉了

但是,这样其实还是不对的,因为无法保证f[i][k]一定能被合成为它表示的数,所以还要标记一下它是否能合成为一个数

if(f[i][k] == f[k + 1][j] && f[i][k] != -1) f[i][j] = max(f[i][j], f[i][k] + 1);

所以最终代码是

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
char read_c() {
    char c = getchar();
    while(c != 'M' && c != 'C') c = getchar();
    return c;
}
int f[250][250], ans;
int main() {
    int n = read(); memset(f, -1, sizeof(f));
    for(int i = 1; i <= n; ++i)
        f[i][i] = read(), ans = max(f[i][i], ans);
    for(int i = n-1; i >= 1; --i)
        for(int j = i+1; j <= n; ++j) {
            for(int k = i; k < j; ++k) {
                if(f[i][k] == f[k+1][j] && f[i][k] != -1) f[i][j] = max(f[i][j], f[i][k] + 1);
                ans = max(f[i][j], ans);
            }
        }
    cout << ans;
    return 0;
}

原文地址:https://www.cnblogs.com/wxl-Ezio/p/11011526.html

时间: 06-12

USACO16OPEN 248的相关文章

洛谷P3146 [USACO16OPEN]248

题目描述 Bessie likes downloading games to play on her cell phone, even though she doesfind the small touch screen rather cumbersome to use with her large hooves. She is particularly intrigued by the current game she is playing.The game starts with a seq

关于H.248的树图规则

一.H248数图 数图可以是一个字符串,我们不妨称之为数图字符串,它遵循了Unix系统命令中的规则表达式的语法规定,也可以是许多数图字符串的并集,之间用“|”分隔,我们不妨称之为数图字符串列表.以下是一个数图的例子: [2-8]xxxxxxx | 13xxxxxxxxx | 0xxxxxxxxx | 9xxxx | 1[0124-9]x | * | # | x.# | [0-9*#].T 我们结合对该数图的分析,学习一下怎样读懂一个数图.首先,我们对一个数图字符串中可能出现的字符进行一下归纳.

Solaris 64bit (Sparc) 平台下,oracle 软件的bug ,实例启动248天会导致 db 或者asm crash

Bug 10194190 - Solaris: Process spin and/or ASM and DB crash if RAC instance up for > 248 days (Doc ID 10194190.8)

Welcome to Swift (苹果官方Swift文档初译与注解三十五)---248~253页(第五章-- 函数 完)

Function Types as Return Types (函数类型作为返回值类型) 一个函数的类型可以作为另一个函数的返回值类型.可以在一个函数的返回值箭头后面写上一个完整的函数类型. 例如: 下面的例子定义了两个简单的函数,分别为stepForward 和 stepBackward.其中stepForward函数返回值比它的输入值多1,stepBackward函数返回值比它输入值少1.这两个函数的 类型都是(Int) -> Int: func stepForward(input: Int

Codeforces Round #248 (Div. 1)——Nanami&amp;#39;s Digital Board

题目连接 题意: 给n*m的0/1矩阵,q次操作,每次有两种:1)将x,y位置值翻转 2)计算以(x,y)为边界的矩形的面积最大值 (1?≤?n,?m,?q?≤?1000) 分析: 考虑以(x,y)为下边界的情况,h=(x,y)上边最多的连续1的个数.那么递减的枚举,对于当前hx,仅仅须要看两側能到达的最远距离,使得h(x,ty)不大于h就可以.之后的枚举得到的两側距离大于等于之前的,所以继续之前的两側距离继续枚举就可以. const int maxn = 1100; int n, m, q;

bzoj4580: [Usaco2016 Open]248

bzoj4580: [Usaco2016 Open]248 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 23  Solved: 21[Submit][Status][Discuss] Description Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumber

BZOJ 4580: [Usaco2016 Open]248

Description 一个序列,每次可以把相邻的两个数合为一个,价值+1,求最后的最大价值. Sol 区间DP. \(f[i][j]\) 表示 \(i-j\) 中合成一个数字为多少,转移就是枚举断点,断点两边的价值一样,就合并. 复杂度 \(O(n^3)\) Code /************************************************************** Problem: 4580 User: BeiYu Language: C++ Result: Ac

[USACO16OPEN]关闭农场Closing the Farm(洛谷 3144)

题目描述 Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporarily close down his farm to save money in the meantime. The farm consists of  barns connected with  bidirectional paths between some pairs of barn

洛谷P3143 [USACO16OPEN]钻石收藏家Diamond Collector

题目描述 Bessie the cow, always a fan of shiny objects, has taken up a hobby of mining diamonds in her spare time! She has collected  diamonds () of varying sizes, and she wants to arrange some of them in a pair of display cases in the barn. Since Bessie

248. Strobogrammatic Number III

题目: A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high. For example,Given low = "5