spoj混合:需要关于逻辑的帮助
这个问题要求尽量减少产生的烟雾。
我的方法:因为在任何时候，只有相邻的混合物会被捡起。所以我试着用dp。就像我知道n-1混合物的答案一样，我可以得到n个混合物的答案。
如何？：第n种混合物要么是
案例1:与(n-1)th混合物混合，其结果与1 n-2混合物的合成混合物混合。或
Case2:它将混合成n-1混合物.
让dpi表示第一I混合物的最小烟雾，resi表示第一I混合物的合成混合物。当然，它们将包含优化的值。Ai表示混合的颜色。
所以
Case1: dpi=dpi-2+ Ai-1Ai +resi-2(Ai-1+Ai)%10 0，resi=(resi-2+Ai+Ai-1)%10 0；
对于Case2: dpi = dpi-1 + resi-1*Ai；和resi = (resi-1+Ai)%100；
基本案例：
如果只有1种混合物，给出的烟雾=0，所产生的混合物本身就是混合物。如果只有2种混合物给出烟雾= A*A1和resuilt = (A+A1)%100
我的代码:在4个案例中，它只通过了一个(不是样本测试用例)--我的逻辑哪里出错了？
问题陈述
哈利波特面前有n个混血，排成一排。每种混合物都有100种不同的颜色(颜色的数字从0到99)。
他想把所有这些混合物混合在一起。在每一步，他将采取两种混合物站在一起，并将它们混合在一起，并将产生的混合物放在他们的位置。
当混合两种颜色a和b时，产生的混合物将具有颜色(a+b) mod 100。
而且，在这个过程中会有一些烟雾。混合两种颜色a和b时产生的烟雾量为a*b。
找出哈利在混合所有混合物时所能产生的最小烟雾量。
输入中将有许多测试用例。
每个测试用例的第一行将包含n、混合物数、1 <= n <= 100。
第二行包含0到99之间的n个整数--混合物的初始颜色。
输出每个测试用例，输出最小烟雾量。
示例
输入：
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;
}回答 1
Stack Overflow用户
发布于 2020-06-15 01:18:55
您的代码输出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代码被接受了.
我们可以使用两种思想：(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:
breakhttps://stackoverflow.com/questions/62357108
复制相似问题
腾讯云开发者
