EatWalnuts(评测)

As we all know, in the ACM ICPC held in 2017, the organizer of Xinjiang University presented a box of walnuts to each coach. Our coach is happy to share with the team members except Mr.Watermelon. He is going to test Mr.Watermelon with a game when Mr.Watermelon want to eat some walnuts.

He put some walnuts in a row and let Mr.Watermelon pick one of them. And this walnut is not the ﬁrst or last in the queue. The price Mr.Watermelon need to pay is : the walnut, the walnut in front of the walnut, and the walnut behind the walnut , the square of the sum of the size of these three walnuts.

For example, now there is a row of walnuts in front of Mr.Watermelon. Their size is: 3 1 50 20 15. If this time Mr.Watermelon picked the third walnut. He needs to pay (1 + 50 + 20) ∗ (1 + 50 + 20) = 5041.

After a walnut is taken away, it will leave the queue. Then Mr.Watermelon picks a walnut again until only two walnuts remain in the queue.

Mr.Watermelon wants to know what the minimum price he will pay when he takes walnuts until there are only two walnuts in the queue. But he needs more time to spend with his girlfriend. So he ask you to help him calculate this problem.

Input contains multiple test cases.The ﬁrst line of each test case contains a integer n(3 ≤ n ≤ 100), the number of walnuts at the beginning. The second line contains n positive integers separated by spaces, representing the size of each walnut. Each positive integer does not exceed 1,000.

For 50% of the testcases, n ≤ 50.

For 90% of the testcases, n ≤ 90.

For 100% of the testcases, n ≤ 100.

The number of the testcases does not exceed 1000.

#include <bits/stdc++.h> using namespace std; int f[105][105],a[1005]; inline int mul(int x){return x*x;} int main (){ int n,d,i,k; while (scanf ("%d",&n)!=EOF) {for (i=1;i<=n;i++) {scanf ("%d",&a[i]);} for (d=3;d<=n;d++) {for (i=1;i+d-1<=n;i++) {int j=i+d-1; f[i][j]=2147483647; for (k=i+1;k<j;k++) {f[i][j]=min(f[i][j],f[i][k]+f[k][j]+mul(a[i]+a[j]+a[k]));} } } printf ("%d\n",f[1][n]); } return 0; }

详情