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

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

洛谷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

[luoguP3146] [USACO16OPEN]248(区间DP)

传送门 f[i][j]表示区间 i-j 合并的最大值 转移: 若f[i][k] && f[k+1][j] && f[i][k] == f[k+1][j] --> f[i][j] = max(f[i][k]+1,f[i][j]) 但要注意, 若f[i][k]!=f[k+1][j],那么无法进行转移 代码 #include <cstdio> #include <iostream> #define max(x, y) ((x) > (y) ?

luogu P3146 [USACO16OPEN]248

基础区间的dp题 状态很容易得出:dp[i][j]表示区间i--j可以合成的最大数. 状态转移方程很显然:if (dp[i][k]==dp[k+1][j]) dp[i][j]=max(dp[i][j],dp[i][k]+1) 那么只需要先枚举结点,在以该结点为中心向两边枚举长度即可,但一次循环不能保证所有数据都正确,因为后得出的区间可能更新前得出的区间. 为了解决问题,跑多次循环 #include<iostream> #include<cstdio> #include<cma

luogu3146 [USACO16OPEN]248

细节被坑惨 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+5; 4 const int INF=1e9+7; 5 int n,ans,dp[305][305]; 6 template <class t>void red(t &x) 7 { 8 x=0; 9 int w=1; 10 char ch=getchar(); 11 while(ch<'0'||ch>'9') 1

P3146 [USACO16OPEN]248

实际上1*n的地图..不就是线性的么.. 1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 using namespace std; 8 int n,m,ans; 9 int f[270000][66],a[270000]; 10 int ma

做题单

错误 收藏了过多题目 QWQ P1383 高级打字机 P1270 “访问”美术馆 P1481 魔族密码 P1280 尼克的任务 P1271 聚会的快乐 P3631 [APIO2011]方格染色 P1243 排序集合 P2858 [USACO06FEB]奶牛零食Treats for the Cows P3146 [USACO16OPEN]248 P2890 [USACO07OPEN]便宜的回文Cheapest Palindrome P1896 [SCOI2005]互不侵犯 P3154 [CQOI2

关于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)