因为要求字典序最小,所以如果有多种方案应该让不同情况即使所得值一样大也要替换。
by 断线鸢 @ 2019-03-13 12:42:29
只是把
```cpp
if(dp[j] >= dp[j - k] + a[i][k]) continue;
```
改成了
```cpp
if(dp[j] > dp[j - k] + a[i][k]) continue;
```
就删了一个”=“。
by kcn999 @ 2019-03-13 12:42:36
顺推的写法就是要这样改
by 断线鸢 @ 2019-03-13 12:43:44
@[勿忘。。。](/space/show?uid=64086)
可能是我对题目中的字典序的理解有问题?
刚刚想到了一个数据:
```
1 3
10000 10 10000
```
按照我的理解输出应该是:
```
10000
1 1
```
可实际上那个AC程序的输出:
```
10000
1 3
```
???
by kcn999 @ 2019-03-13 12:53:07
@[kcn999](/space/show?uid=77784)
by 断线鸢 @ 2019-03-31 13:44:59
应该是
10000
1 3
我的程序也是
by 断线鸢 @ 2019-03-31 13:45:30
我也想到了一个样例:
```cpp
2 3
1 4 4
1 4 4
```
不加等号:
```cpp
5
1 2
2 1
```
加了等号:
```cpp
5
1 1
2 2
```
在此样例中,加等号字典序最小。
但是在
```cpp
1 3
10000 10 10000
```
中加等号字典序并非最小。
所以事实证明:加等号只能恰好通过LG的样例,并不一定能使字典序最小。
by Mini_PEKKA @ 2022-12-17 16:20:10