題目鏈接
題意：給你一組數，如果前一個數等于后一個數，這兩個數就可以合成一個新數，并且新數的值為原數加1，問得到陣列的最小長度
區間dp題，難度在于連續多個相同的數任意兩兩合并怎么區別表示，
#include <iostream>
#include <cstring>
using namespace std;
#define mann 0x3f3f3f3f
long long int n,t,k,x,m,i,j;
long long int mod=998244353;
long long int a[1005][1005],d[1005][1005];
using namespace std;
string s;
int main()
{
cin>>n;
for(i=1; i<=n; i++)
{
cin>>a[i][i];//為了區分連續的多個相同的數（如：333）之間任意的兩兩和成情況，二維陣列第一個表示初位置，第二個表示末位置，
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
d[i][j]=j-i+1;//記錄區間長度
}
for(int len=2; len<=n; len++)
{
for(int i=1,j=len+i-1; j<=n; j++,i++)
{
for(int k=i; k<j; k++)
{
if(d[i][k]==1&&d[k+1][j]==1&&a[i][k]==a[k+1][j])//判斷是否是相鄰的兩個數，兩個數是否相等
{
d[i][j]=1;//i,j兩個數合并成了一個
a[i][j]=a[i][k]+1;//原位置i,j兩個數合并后的新值
}
d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);//更新長度，如果有合并情況就取小的
}
}
}
cout<<d[1][n]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279387.html
標籤：其他
下一篇：問個有關編碼器的問題