能量项链__牛客网

Java

wyllyh123456

卡死在了案例7🤣😂😂😂做不来呀

发表于 2022-03-21 16:23:11 回复(0)

Darkraid

用例7过不了的，多半是取模的问题，long long int和int表示的同一个数对1e9+7取模的结果居然不一样（有大神讲讲这是为什么吗？）

发表于 2023-02-11 15:19:01 回复(0)

pein531

经典区间DP，首先把数组扩充一倍，将环形DP转成线性DP。不过在本题中分割点k是左右两边共用的，它既是左边珠子的尾标记，也是右边珠子的头标记。
因此状态转移应该为：dp[l][r] = dp[l][k]+dp[k][r]+w[l]×w[k]×w[r]

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;
int w[N], f[N][N], mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i + n] = w[i];
    }
    for(int len = 3; len <= n + 1; len++) {
        for(int l = 1; l + len - 1 <= n << 1; l++) {
            int r = l + len - 1;
            for(int k = l + 1; k < r; k++) {
                f[l][r] = max(f[l][r], (w[l]*w[k]*w[r] + f[l][k] + f[k][r]) % mod);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, f[i][i + n]);
    }
    cout << ans << endl;
}

发表于 2022-07-08 15:02:59 回复(0)

牛客212561046号

就离谱，开辟数组空间为2*n, 下标从0开始案例7就过不了。开辟数组空间为2*n+1，下标从1开始就可以

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9+7;
int main() {

    int n; cin>>n;
    vector<int> arr(2*n+1);
    for(int i=1; i<=n; i++){
        cin>>arr[i];
        arr[i+n] = arr[i];
    }
    //dp[i][j]为arr[i~j]的矩阵连乘最大值
    vector<vector<int>> dp(2*n+2, vector<int>(2*n+2,0)); 
    for(int len=3; len<=n+1; len++){
        int L=2*n-len+1;
        for(int l=1; l<=L; l++){
            int r=l+len-1;
            for(int k=l+1; k<r; k++){
                dp[l][r] = max(dp[l][r],(dp[l][k]+dp[k][r]+arr[l]*arr[k]*arr[r])%MOD);
            }
        }
    }
    int res=0;
    for(int l=1; l<=n; l++){
        res = max(res,dp[l][l+n]);
    }
    cout<<res;
    return 0;
}

编辑于 2024-01-03 16:22:31 回复(0)

昊天明月

最大值取余后的值并不一定还是最大值啊，所以不要在max时取余，可是我最后才取余案例7也过不了啊。

发表于 2023-10-08 16:46:33 回复(0)

Python3

不想上班艾伦是单身

num = int(input())

stack = [int(item) for item in input().split()]

stack_r = [0]

for i in stack:

stack_r.append(i)

for i in stack:

stack_r.append(i)

dp = [[0]*(2*num+1) for i in range(2*num+1)]

for leng in range(2,num+2,1):

for i in range(1,2*(num)-leng+2,1):

ends = i+leng-1

for j in range(i+1,ends,1):

dp[i][ends] = max(dp[i][ends],(stack_r[i]*stack_r[j]*stack_r[ends]+dp[i][j]+dp[j][ends])%(1e9+7))

big =0

for i in range(1,num+1):

big = max(big,dp[i][i+num])

print(int(big))

第七个不过，什么情况？

发表于 2022-12-20 23:29:57 回复(0)

C++

牛客288355985号

递归卡样例7，是不是只有递推的那种取模顺序才对。

#include<iostream>
#include<utility>
using namespace std;

const int MOD=1e9+7;
int arr[209];

long long cache[209][209];
long long dp(int l,int r){
  if(cache[l][r]!=0) return cache[l][r];
  long long maxe=0;
  for(int i=l+1;i<r;i++){
    long long e=(arr[l]*arr[i]*arr[r]+dp(l,i)+dp(i,r))%MOD;
    maxe=max(maxe,e);
  }
  return cache[l][r]=maxe;
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>arr[i];
    arr[i+n]=arr[i];
  }
  long long maxe=0;
  for(int i=0;i<n;i++){
    maxe=max(maxe,dp(i,i+n));
  }
  cout<<maxe<<endl;
}

发表于 2022-09-02 13:18:26 回复(0)

Java

LaiNN

案例

8

7 18 16 14 16 7 13 10

预期输出22176是不是错了，怎么算都是21582

发表于 2022-04-28 16:50:49 回复(0)

能量项链

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题