Educational Codeforces Round 83 (Rated for Div. 2) E. Array Shrinking
葫芦聚聚说可以n^2搞。。
还好没卡我n^3 的做法。。
核心思路就是f[i]表示 前i个数最小能分成几个数。
然后由于前i个数都分好了，我们只需要取min f[k]+1( 满足k<i且[k+1,i]可以合成一个数 ) 即可。
其中判断我是用区间dp预处理 On^3
但葫芦聚聚说直接用栈，然后利用差量 就可以优化到ON^2
明天再学 先记下来
下面是On^3 的做法
#include
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<>n;
for(int i=1;i>a[i],dp[i][i]=a[i];
for(int len=1;len<=n;len++)
{
for(int l=1;l<=n;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
if(dp[l][k]==dp[k+1][r]&&dp[l][k])dp[l][r]=dp[l][k]+1;
// cout<<l<<" "<<r<<endl;
}
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
{
if(dp[1][i])
{
f[i]=1;
continue;
}
for(int l=2;l<=i;l++)
{
if(dp[l][i])
f[i]=min(f[l-1]+1,f[i]);
}
// cout<<i<<" "<<f[i]<<endl;
}
cout<<f[n]<<endl;
return 0;
}
作者：夕林山寸
相关文章
Efia
2020-10-24
Rasine
2020-05-09
Rayna
2022-10-26
Kamiisa
2022-11-04
Naomi
2022-11-06
Zahara
2022-11-06
Gytha
2022-11-06
Winona
2022-11-06
Diane
2022-11-06
Kathy
2022-12-03
Kara
2022-12-25
Tanisha
2023-02-12
Dorothy
2023-02-26
Haidee
2023-02-26
Rose
2023-02-28
Elina
2023-02-28
Serafina
2023-03-09