完全背包
之前学习了如何解01背包问题，用的是二维解法，今天学习的是01背包的一维解法。
其实一维解法，就是在第二个for循环（背包循环）使用逆序，同时状态转移方程不再用dp[ i-1 ][ j ]这样的样式表示，而是直接使用如dp[ j ]。
完整的状态转移方程：dp[ j ] = max( dp[ j ]，dp[ j-w[ i ] ] + v[ i ] )
完全背包与01背包主要的区别在于，物品可以无限次数的取。要做到这一点，需要将第二个循环使用正序。（其实完全背包的两个循环可以互换位置）。
将正序的状况写一下：
//外层循环为物品，内层循环为背包
for(int i=1;i<=n;i++){for(int j = w[i] ;j<= m;j++){//内部为状态转移方程}}二分
（ 洛谷题 P2759 奇怪的函数 出错了 - 洛谷 ）
今天还学习了二分。其实二分在最开始学习C语言的时候就学到了。今天在写一个题目时用到，有需要注意的地方。
题目为：一个n位数，x^x要满足达到n位数，求满足条件的最小x
这题的数据非常大，所以会通过二分法。同时要知道x^x的位数是多少。
通过二分法得到一个数，再求其位数。（根据实际情况不断调整mid）
这里就可以通过推算得知（位数） len = (long long)mid * log10(1.0 * mid) + 1;
二分法的调整：
if (n > len) {
left = mid + 1;
}
else {
right = mid;
}
这里重点需要注意的一点就是此处的right不能调整为 right = mid-1 ;
（下面部分也是我自己找来的解释，需要多理解理解）
关于 mid = right - 1 与 mid = right
若使用 mid = right - 1 的话，可能会导致有些边界值被跳过。
- 使用
mid = right可能会一直定位到最后一个符合条件的数，保证了搜索不漏掉任何可能的值。 mid = right - 1可能在某些情况下（尤其是当 left 非常接近right）会跳过最后的有效值，从而得不到正确的结果。-
总结
- 所以，在正确实现二分查找时，左右边界的定义和调整都应该非常小心，以保证不会遗漏任何可能的符合条件的答案。在这个上下文下，使用
mid = right是为了保证搜索范围能更准确地定位到我们想要的最小值，从而输出所需的结果。
代码也贴一下：
#include<stdio.h>
int main() {int n = 0;scanf("%d", &n);long long left = 1;long long right = 2e9;long long len = 0;long long mid = 0;while (left < right) {mid = (left + right)/2 ;len = (long long)mid * log10(1.0 * mid) + 1;if (n > len) {left = mid + 1;}else {right = mid;}}printf("%d", left);return 0;
}
