问题要求尽量减少烟雾的产生。
我的方法是： 因为在任何时候，只有相邻的混合物才会被接收。所以我尝试使用dp。如果我知道n-1种混合物的答案，我可以得到n种混合物的答案。
如何得到答案？
案例1:与(n-1)个混合物混合，其结果与第n-2个混合物的结果混合。或
情况2: 它将混合n-1种混合物的结果混合物。
让dp[i]表示前i种混合物的最小烟雾，res[i]表示前i种混合物的结果混合物。当然，它们将包含最佳值。而A[i]表示第i种混合物的颜色。
所以
对于Case1：dp[i]=dp[i-2]+A[i-1]A[i] + res[i-2](A[i-1]+A[i])%100；而res[i]=(res[i-2]+A[i]+A[i-1])%100。
对于Case2：dp[i]=dp[i-1]+res[i-1]*A[i]；res[i]=(res[i-1]+A[i])%100。
基本情况。
如果只有1种混合物给定的烟雾=0，结果混合物是混合物本身.如果只有2种混合物给定的烟雾=A[0]*A[1]，并且重新构建=(A[0]+A[1])%100。
我的代码：4个案例中，只通过了1个（不是样本测试案例）我的逻辑哪里出了问题？
哈利波特面前有n种混合物，排列成一排。每种混合物都有100种不同的颜色（颜色的数字从0到99）。
他要把所有这些混合物混合在一起。在每一步，他都要把两个相邻的混合物混合在一起，并把得到的混合物放在它们的位置上。
当混合两种颜色a和b的混合物时，得到的混合物的颜色将是（a+b）模数100。
另外，在这个过程中还会产生一些烟雾。混合两种颜色a和b的混合物时，产生的烟雾量是a*b。
找出当哈利将所有混合物混合在一起时能得到的最小烟雾量是多少。
输入在输入中会有许多测试用例。
每个测试案例的第一行将包含n，即混合物的数量，1 <= n <= 100。
第二行将包含n个0到99之间的整数--混合物的初始颜色。
输出对于每个测试用例，输出最小的烟雾量。
输入：
2
18 19
3
40 60 20
输出。
342
2400
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n; //no. of mixtures
int A[n];
for(int i=0;i<n;i++)
cin>>A[i]; // filling their values.
if(n==1) //base case
{
cout<<0<<endl;
return 0;
}
long long dp[n],res[n];
dp[0]=0; // for 2 mixtures
res[0]=A[0];
dp[1]=A[1]*A[0];
res[1]=(A[1]+A[0])%100; //
for(int i=2;i<n;i++)
{
long long ans1,ans2,res1,res2;
ans1=dp[i-1]+res[i-1]*A[i];
res1=(res[i-1]+A[i])%100;
ans2=dp[i-2]+A[i-1]*A[i]+res[i-2]*((A[i-1]+A[i])%100);
res2=(res[i-2]+(A[i-1]+A[i])%100)%100;
dp[i]=min(ans1,ans2);
if(dp[i]==ans1)
res[i]=res1;
else
res[i]=res2;
}
cout<<dp[n-1];
return 0;
}
你的代码输出6500为输入 20 10 30 30 40 但正确的结果是3500。
20 10 30 30 40
200/30 900/60
30 60 40
2400/0
30 0
smoke = 200 + 900 + 2400 = 3500
有一个诀窍是要意识到(或学习)任何折叠区间的最终颜色都是一样的，不管它的混合顺序是怎样的。下面的Python代码，利用divid-and-conquer，被接受了。
我们可以利用两个思想（1）由于加法的关联性，我们选择的任何特定区间通过混合折叠到一个元素，无论混合顺序如何，都会导致相同的颜色；（2）给定任何区间（特别是完整列表）的最优混合顺序，由于混合是在相邻颜色之间进行的，所以该区间的最后一个混合一定存在一些最优的单处，换句话说，一个最优的单处，将完整的区间一分为二，使得每一边在最后混合之前都是完全折叠的。
考虑到这两个想法，我们基本上建立了一种 "蛮力 "递归--尝试其中每一个可能的分割，知道每个部分的颜色不是我们需要的一个以上的可能性的维度，并对两个部分的每一个进行同样的递归。希望代码中的基础案例非常清晰。
import sys
# Returns (smoke, colour)
def f(lst, i, j, memo):
# Empty interval
if i > j:
return (float('inf'), 0)
# Single element
if i == j:
return (0, lst[i])
if (i, j) in memo:
return memo[(i, j)]
best = (float('inf'), -1)
for k in xrange(i, j):
smoke_l, colour_l = f(lst, i, k, memo)
smoke_r, colour_r = f(lst, k + 1, j, memo)
smoke = smoke_l + smoke_r + colour_l * colour_r
colour = (colour_l + colour_r) % 100
best = min(best, (smoke, colour))
memo[(i, j)] = best
return best
# I/O
while True:
line = sys.stdin.readline()
if line:
n = int(line)
if n == 0:
continue
lst = sys.stdin.readline()
lst = map(int, lst.split())
print f(lst, 0, n-1, {})[0]
else:
break