总所周知思维题=DP
Problem 1
雇佣计划
题目描述
一位管理项目的经理想要确定每个月需要的工人,他当然知道每月所需的最少工人数.当他雇佣或解雇一个工人,会有一些额外支出.一旦一个工人被雇佣,即使他不工作,他也将得到工资.这位经理知道雇佣一个工人的费用,解雇一个工人的费用和一个工人的工资.现他在考虑一个问题:为了把项目的费用工致在最低,他将每月雇佣或解雇多少个工人？
输入格式
第1行：1个整数n(n<=12)，表示月数。
第2行：3个用空格分开的整数h, s, f，分别表示雇佣一个工人的费用；一个工人的月工资和解雇一个工人的费用。
第3行：n个用空格分开的整数，分别表示每个月最少需要的工人数(每个月的工人数<=1000)
输出格式
第1行：1个整数，表示项目的最小总费用
样例
样例输入
3
4 5 6
10 9 11
样例输出
199
打了个假贪心爆零。。。
其实我们可以发现每次雇佣的人都不多于人数要求最多月的值（多买了白吃白喝还要付遣散费），也不能低于当前月需要的人数，那么每个月的最优解根据上一个月得来，所以用DP来解
Code:
#include<cstdio>#include <cstring>#include<iostream>using namespace std;int n,maxn,a[100005];long long h,s,f,dp[15][10005];int main(){scanf("%d%lld%lld%lld",&n,&h,&s,&f);for(int i=1;i<=n;i++){scanf("%d",&a[i]);maxn=max(maxn,a[i]);}memset (dp, 0x3f, sizeof (dp));for(int i=0;i<=maxn;i++){dp[0][i]=i*h;}for(int i=1;i<=n;i++){for(int j=a[i];j<=maxn;j++)//本月人数{for(int k=a[i-1];k<=maxn;k++)//从上月人数到最大人数{dp[i][j]=min(dp[i][j],dp[i-1][k]+(k>=j?(k-j)*f:(j-k)*h));//如果大于，遣返，小于则雇佣}//保持不变的情况包含在了k==j里面dp[i][j]+=j*s;//每个目前还有的人还需要发工资}}long long ans=0x3f3f3f3f;for(int i=a[n];i<=maxn;i++){ans=min(ans,dp[n][i]);//到最后至少有a[n]个人}printf("%lld",ans);}
Problem 2
回文数组
题目描述
给定有N个整数的数组A，下标从1到N。如果对每一个下标i均满足A[i] =A[N-i+1]，则称数组是回文的。
例如，数组A={1,2,3,2,1}就是回文数组。
如果数组A不是回文的，可以采用合并两个相邻元素的方法去得到回文数组。注意，每操作一次，数组的元素数量减少1。
例如，数组A={1,2,3}不是回文数组，但是通过合并A[1]和A[2]，得到{3,3}就是回文数组了。
显然，无论给出怎样的数组元素，最多经过N-1次操作，合并为一个数时，数组A一定是回文数组了。因此，本题一定有解。
然而问题来了：对于给定的数组A，最少经过多少次操作，能让A变成回文数组？
输入格式
第1行：1个整数N，表示数组A的元素个数
第2行：N个空格分开的整数，表示数组A
1 <= N <= 10^6
1 <= A[i] <= 10^9
输出格式
第1行：1个整数，表示最少的操作次数
样例
样例输入
3
1 2 3
样例输出
1
考虑使用双指针，设i从头开始，j从尾开始
1.a[i]==a[j],此时直接i++，j–
2.a[i]!=a[j],此时可以从左边或右边合并元素，那么合并更小的一边更有利接近最小次数（否则差值会更大，回文概率越小）
边界:i=j
Code:
#include<cstdio>#include<iostream>using namespace std;int n,l1,l2,ans;long long a[1000005];int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}l1=1;l2=n;while(l1<l2){if(a[l1]==a[l2]){l1++;l2--;continue;}else{if(a[l1]+a[l1+1]<=a[l2]+a[l2-1]){a[l1+1]=a[l1]+a[l1+1];l1++;}else{a[l2-1]=a[l2]+a[l2-1];l2--;}}ans++;}printf("%d",ans);return 0;}
Problem 3
杯子
重庆八中在80周年校庆的时候获捐个杯子， 每个杯子有两个属性：一个是已装水量 a[i]，一个是可装水量 b[i]
其中 a[i]<=b[i]
从一个杯子向另一个杯子倒 x单位体积的水需要花费的时间是x秒。 现在用n个杯子中的k个来装所有的水， 求最小的k，以及最少花费的时间 。
输出格式
两个正整数， 和 ，分别代表最少的杯子个数和最少花费的时间。
样例
样例1输入
4
3 3 4 3
4 7 6 5
样例1输出
2 6
样例2输入
2
1 1
100 100
样例2输出
1 1
样例3输入
5
10 30 5 6 24
10 41 7 8 24
样例3输出
3 11
数据范围与提示
在第一个样例中，可以把水从第瓶倒到第瓶。需要秒钟，之后，第2瓶将含有 单位的水。然后可以把水从第瓶倒进第瓶，再倒进第瓶：倒个单位的水在第瓶，倒个单位的水在第瓶，需要 秒 ，所以，所有水都会装在个瓶子中，会花掉 秒来完成这件事情。
考场贪心爆零，但DJ贪心错误比我更离谱15pts
总所周知我的贪心不是贪心
很容易想到的是既然要瓶子最小，那么剩余容积越大越好，如果相同，则水越多越好，需要花费的价值一定更小
但是上述思路的错误在于，如果剩余容积大的杯子，水很少，其他杯子的水倒进来不如它倒进别的杯子里去，那么贪心就会出错
那么这时候就不应该只考虑剩余容积，而直接讨论容积与水的关系.
首先利用类似贪心的思路排序，但把剩余容积换成了容积
用一个sum纪录容积的前缀和，如果大于等于了sum水，那么肯定以目前个水杯来装是最少的杯子数
接下来用一个dp[j][k]表示装有j单位体积水时用了选中杯子中的k个所装载的水量
那么用总水量减去每个dp[sum水~sum][所选个数]比个max，就是最少需要的移动水量
Code:
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int n,dp[100005][105],sw,st,least,can,ans;struct ren{int had,full;}a[1005];bool cmp(ren x,ren y){if(x.had!=x.had){return x.had>y.had;}return x.full>y.full;}//贪心部分int main(){memset(dp,-0x3f,sizeof(dp));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i].had);sw+=a[i].had;}for(int i=1;i<=n;i++){scanf("%d",&a[i].full);st+=a[i].full;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){can+=a[i].full;if(can>=sw)//可以装载{least=i;break;}}dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=st;j>=a[i].full;j--){for(int k=1;k<=least;k++){dp[j][k]=max(dp[j][k],dp[j-a[i].full][k-1]+a[i].had);//减去它给总体积的贡献，加上它的水量，即当前所含水}}}for(int i=sw;i<=st;i++)//最少要装sum水这么多{ans=max(ans,dp[i][least]);}printf("%d %d",least,sw-ans);return 0;}
Problem 4
连通分量
题目描述
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。即在一个连通子图中，包含和顶点有关所有的边，那就是极大连通子图；如果包含了必不可少的边，那就是极小连通子图。
例如：一个无向图有5个顶点，1-3-5是连通的，2是连通的，4是连通的，则这个无向图有3个连通分量。
输入格式
第一行是一个整数T，表示有T组测试样例(0 < T <= 50)。每个测试样例开始一行包括两个整数N，M，(0 < N <= 20,0 <= M <= 200)
分别代表N个顶点，和M条边。下面的M行，每行有两个整数u，v，顶点u和顶点v相连。
输出格式
每行一个整数，连通分量个数。
样例
样例输入
2
3 1
1 2
3 2
3 2
1 2
样例输出
2
1
简单DFS，不多赘述
#include<cstdio>#include<iostream>#include<cstring>using namespace std;int t,n,m,head[],cnt,ans;bool vis[];struct ren{int to,next;}a[];void add(int x,int y){a[++cnt].to=y;a[cnt].next=head[x];head[x]=cnt;}void dfs(int now){vis[now]=1;for(int i=head[now];i;i=a[i].next){int v=a[i].to;if(!vis[v]){dfs(v);}}}int main(){scanf("%d",&t);while(t--){ans=0;memset(vis,0,sizeof(vis));memset(head,0,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i=1;i<=n;i++){if(!vis[i]){ans++;dfs(i);}} printf("%d\n",ans);}}
