@[boolex](/user/644860)
```cpp
for(int k = n; k>=vv; k--)
for(int j = vv; j<=n; j++)
```
这个循环中的语句可以认为执行了 $n^2$ 次,所以复杂度是 $\mathcal O(mn^2)$ 的,会 T。
事实上这题有特殊性:
>他还从因特网上查到了每件物品的价格(都是 $10$ 元的整数倍)。
可以借此优化。
by 阿丑 @ 2022-05-19 16:47:41
已经解决了,即背包九讲中P02“一个简单有效的方法”,把价格不同,而重要性一样的物品只保留一件,核心代码如下
```cpp
fffsize = 0;
for(int j = vv-1; j<=n; j++)//细节vv-1,因为第一个数是肯定要的,所以vv-上一个1就可以把这个数也带进来。相当于一个没有附件的物品,也会被放进fff中
if(ff[j+1]>ff[j])
{
fffsize++;
fff[fffsize].v = j+1;
fff[fffsize].w = ff[j+1];
}
```
[完整AC代码](https://www.luogu.com.cn/paste/2z4ghtpn)
by boolex @ 2022-05-19 17:02:45