使用C++实现:有一个序列A,其中第i位为A[i]。输入一个正整数n表示序列长度。输入n个数表示序列中的数。已知若r-l>=2,F(l,r)=F(l+1,r-1)+(若A[l]≠A[r]则该值为1,否则为0),特别的,而当l=r时,F(l,r)=0, 当l=r-1时,F(l,r)=(若A[l]≠A[r]则该值为1,否则为0), 请在O(nlogn)时间内计算对于所有1<=i<=j<=n, F(i,j)之和。写一份C++代码帮我完成这个问题。
时间: 2023-03-10 20:43:00 浏览: 104
请参考以下C 代码:#include<stdio.h> int A[1000];
int c[1000][1000];
int F[1000][1000]; int count(int l, int r)
{
if (l >= r)
return 0;
int& ans = c[l][r];
if (ans != -1)
return ans;
ans = count(l + 1, r);
for (int i = l + 1; i <= r; i++)
{
if (A[l] != A[i])
ans += count(l + 1, i - 1) + 1;
}
return ans;
} int sum(int l, int r)
{
if (l > r)
return 0;
int& ans = F[l][r];
if (ans != -1)
return ans;
ans = sum(l, r - 1) + count(l, r);
return ans;
} int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &A[i]);
memset(c, -1, sizeof c);
memset(F, -1, sizeof F);
int ans = sum(0, n - 1);
printf("%d", ans);
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)