记录一下今日份刷题，一道简单01背包问题+简单的字符串相关题。
在刷题前看了《算法笔记》里动态规划的相关命题，所以那道背包题，基本就是套了个模板。
另一道字符串的题目，我是怎么也没想到，居然还可以这样，进而更加知道了自己有多孤陋寡闻。
- 题源洛谷 P1049
题目描述
有一个箱子容量为V（正整数， 0≤V≤20000），同时有n个物品（0<n≤30）
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入：
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出：1个整数，表示箱子剩余的空间
样例： 输入 24 6 8 3 12 7 9 7 输出：0
我一开始一看，和原来的01背包问题太像了吧，甚至更简单？？我觉得可能不用那么麻烦，就在捉摸，感觉题意是求在放第i个前消耗的空间最大，不由的让我想到了同样可用dp做的最大连续子序列和，但是他又限制了这个和的最大值。我就尝试控制一下，dp[i]初值设为w[i]的值，如果带上第i个物品，消耗空间小于V，则加上，如果大于V，就不加上，然后就出现了问题....因为有可能带上了第i个物品，其他挑着带，有可能值也会更大，想想这个转移方程有很大的逻辑问题啊，还是回到背包问题上吧。发现这道题，只要把原问题的c[i]设成w[i]即可求得最大的消耗的空间。
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=30;
const int maxv=20000;
int dp[maxv],w[maxv];
int main()
{
int V,n;
cin>>V>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
for(int v=0;v<=V;v++)
dp[v]=0;
for(int i=1;i<=n;i++)
{
for(int v=V;v>=w[i];v--)
{
dp[v]=max(dp[v],dp[v-w[i]]+w[i]);
}
}
int max=0;
for(int v=0;v<=V;v++)
{
if(dp[v]>=max)
{
max=dp[v];
}
}
int ans=V-max;
cout<<ans;
}
2.题源 洛谷P1049
题目描述：设有n个正整数(n≤20)，将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13,312,343联接成的最大整数为：34331213
又如：n=4时，4个整数7,13,4,246联接成的最大整数为：7424613
输入：3 13 312 345 输出：34331213
哇 看到这个题，第一反应，依次比较输入数字的大小，从高位到低位，高位数字越高则排在前面然后依次输出
但是我真的想用这个逻辑实现的时候，发现问题很大，我需要把每个输入的数都除以10，然后还要把余数存储，然后不停的除...我想，这个方法还是算了，转成字符串的会不会好一点，就想先把数字存int数组里，然后定义循环里依次再转成string拼接，拼接了之后再转int比较大小，留最大的一个...然后我卡在了int string互转....我网上也搜了很多办法，但是都太emmm，于是我不甘心的百度了这道题，看到了大佬的解法，我才恍然大悟，原来字符串直接拼接也能比较啊喂！！！！原理应该是因为阿斯克编码，数越大，对应的值也越大。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void swap(string &a,string &b)
{
string c;
c=a;
a=b;
b=c;
}
int main()
{
int n;
cin>>n;
string a[21];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-1;j++)
{
if(a[j]+a[j+1]<a[j+1]+a[j])
swap(a[j],a[j+1]);
}
}
for(int i=0;i<n;i++)
cout<<a[i];
}
这里直接用了冒泡，n-1次循环得到最大值，大佬太强了，膜拜！！！！！
后面打算做P1308 统计单词数，又是字符串题，我的字符串相关的真的是无比薄弱了。。。
