Ski Lift 缆车支柱
Description
Farmer Ron in Colorado is building a ski resort for his cows (though budget constraints dictate construction of just one ski lift). The lift will be constructed as a monorail and will connect a concrete support at the starting location to the support at the ending location via some number of intermediate supports, each of height 0 above its land. A straight-line segment of steel connects every pair of adjacent supports. For obvious reasons, each section of straight steel must lie above the ground at all points. Always frugal, FR wants to minimize the number of supports that he must build. He has surveyed the N (2 <= N <= 5,000) equal-sized plots of land the lift will traverse and recorded the integral height H (0 <= H <= 1,000,000,000) of each plot. Safety regulations require FR to build adjacent supports no more than K (1 <= K <= N - 1) units apart. The steel between each pair of supports is rigid and forms a straight line from one support to the next. Help FR compute the smallest number of supports required such that: each segment of steel lies entirely above (or just tangent to) each piece of ground, no two consecutive supports are more than K units apart horizontally, and a support resides both on the first plot of land and on the last plot of land.
科罗拉州的罗恩打算为他的奶牛们建造一个滑雪场，虽然需要的设施仅仅是一部缆车．建造一部缆车，需要从山脚到山顶立若干根柱子，并用钢丝连结它们．你可以认为相对于地面，柱子的高度可以忽略不计．每相邻两根柱子间都有钢丝直接相连．显然，所有钢丝的任何一段都不能在地面之下． 为了节省建造的费用，罗恩希望在工程中修建尽可能少的柱子．他在准备修建缆车的山坡上迭定了N(2≤N≤5000)个两两之间水平距离相等的点，并且测量了每个点的高度H(O≤日≤10^9)．并且，按照国家安全标准，相邻两根柱子间的距离不能超过K(1≤K≤N-1)个单位长度．柱子间的钢丝都是笔直的. 罗恩希望你帮他计算一下，在满足下列条件的情况下，他至少要修建多少根柱子：首先，所有的柱子都必须修建在他所选定的点上，且每一段钢丝都必须高于地面或者正好跟地面相切．相邻两根柱子的距离不大于K个单位长度．当然，在第一个点与最后一个点上一定都要修建柱子．
Input
-
Line 1: Two space-separate integers, N and K
-
Lines 2…N+1: Line i+1 contains a single integer that is the height of plot i.
第1行：两个整数N和K，用空格隔开．
第2到N+1行：每行包括一个正整数，第i+l行的数描述了第i个点的高度．
Output
- Line 1: A single integer equal to the fewest number of lift towers FR needs to build subject to the above constraints
输出一个整数，即罗恩最少需要修建的柱子的数目．
Sample Input 1
13 4
0
1
0
2
4
6
8
6
8
8
9
11
12
样例的图形如下：
可知我们要求最少用多少个柱子，由于条件要求我们选的相邻的两个柱子的水平距离不能超过K，所以，首先考虑一下我们，能使用贪心的思想吗？
如果我们每次都选择当前位置能到达的最远的位置，那么是否就能得到最优解呢？
假如我们使用贪心，那么答案如下：
可知这样我们需要建6根柱子，不是最优解，为什么呢？
就是因为我们的贪心，让我们走到了一个低洼地点，导致我们的解法不是最优的。
所以可以确定这道题目是DP问题。
我们要求到达最后一个点所需要的柱子数量。
那么我们的状态转移是不是要考虑dp[ i ] 的最小值呢？
可知dp[ i ] = min{ dp[i-k], dp[i-k+1], dp[i-k+2], …, dp[i-1] }+1
找到了这个状态转移的条件，那么我们就可以使用DP解决该题了。
要注意我们检测从 j 到 i 这两个柱子间能不能扯线时，要遍历中间所有点的高度，会比较慢。
那么我们应尽可能的减少，检查的次数。
于是先判断，如果我们从 j 这个柱子到 i 这个柱子，会不会使到达 第 i 个柱子用的柱子更少，如果可以，那么我们才去检查能不能在 j 到 i 扯线。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=5001;
int n,k;
//a 数字用来储存高度
int a[maxn];
//dp 数组用来记录到达当前节点，我们最少使用多少个柱子。
int dp[maxn];
// check 函数用来检查，我们是否可以在 i 到 j 之间扯线。
bool check(int s,int e)
{
double h1=a[s],k=(a[e]-a[s])*1.0/(e-s);
for(int i=s+1;i<e;i++)
{
h1+=k;
if(h1<a[i]&&fabs(h1-a[i])>0.0000001)return 0;
}
return 1;
}
void out()
{
for(int i=1;i<=n;i++)
{
cout<<dp[i]<<" ";
}
cout<<endl;
}
int main()
{
// freopen("in.txt","r",stdin);
while(~scanf("%d %d",&n,&k))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//首先把dp 数组初始化为正无穷，因为我们一会儿要使用 min 来更新我们的 dp 数组
memset(dp,0x3f,sizeof(dp));
//可知dp [1] 和 dp[2] 的值一定是 1 和 2，那么首先初始话掉， 方便处理
dp[1]=1;
dp[2]=2;
// 从dp[ 3 ] 开始计算。
for(int i=3;i<=n;i++)
{
//s表示我们如果要求 dp [ i ] ,那么可能到达 i 的 最左边的那个柱子是谁。
int s=i-k;
if(s<1)s=1;
for(int j=s;j<i;j++)
{
//因为检查能不能扯线比较慢，那么我们先检查能不能优化
if(dp[i]>dp[j]+1)
{
//如果能优化，并且可以扯线的话，我们就去优化 dp[ i ]
if(check(j,i))
{
dp[i]=dp[j]+1;
}
}
}
//out();
}
printf("%d\n",dp[n]);
}
return 0;
} 拯救小矮人
Description
一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+…+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。
Input
第一行一个整数N， 表示矮人的个数，接下来N行每一行两个整数Ai和Bi，最后一行是H。（Ai，Bi，H<=10^5）
Output
一个整数表示对多可以逃跑多少小矮人
Sample Input 1
样例1
2
20 10
5 5
30
样例2
2
20 10
5 5
35
Sample Output 1
样例1
2
样例2
1
Hint
数据范围
30%的数据 N<=200
100%的数据 N<=2000
首先上一个大佬的代码打份注释：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2010
using namespace std;
struct use
{
int a,b;
}p[N];
int n,f[N],ans,h,sum;
bool cmp(use &x,use &y)
{
return x.a+x.b<y.a+y.b;
}
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&n);
for (int i=1; i<=n; i++)
{
scanf("%d%d",&p[i].a,&p[i].b);
sum+=p[i].a;
}
scanf("%d",&h);
memset(f,-1,sizeof(f));
sort(p+1,p+n+1,cmp);
f[0]=sum;
//遍历n个想要出去的小矮人
for (int i=1; i<=n; i++)
{
//遍历已经出去了的个数，看看当前第 i 个小矮人能在第几个人后边出去
for (int j=ans; j>=0; j--)
{
//如果第 i 个小矮人，能在第 j 个人后边出去，让我们看看，
//让他替换原来第 j +1个人出去的那个人能不能使坑内的高度更高。
//如果发现 第 i 个小矮人 在第 j+1 个出去更好，那么我们就更新 f。
//使用第 i 个小矮人代替原来那个第 j +1 的那个小矮人出去。
//如果代替后，使坑中当时剩余的高度更高了，那么出去的人就更可能会更多
if (f[j]+p[i].b>=h)
{
f[j+1]=max(f[j+1],f[j]-p[i].a);
}
//如果下一个人坑内的高度被跟新过，说明可以出去i个人，那么ans++
if (f[ans+1]>=0) ans++;
}
}
cout<<ans<<endl;
return 0;
} 看过代码后大致明白了思路，下面是我的解释和代码：
大家都说这是个贪心加DP，也算是比较有道理的吧。
因为我们首先基于一个事实，如果坑内现在有两个小矮人，我们想让他们出去的人更多，那么我们怎么办呢？
我们首先定义一下小矮人的能力大小的概念：
我们认为身体高度加手臂长度越大这个小矮人的爬出去的能力越强。
由贪心的思想我们可以想出，先让能力弱的人站在能力强的人的肩膀上爬出去。
让后能力强的最后爬出去，这样使出去的人数最大。
但是由于小矮人奇怪的人设，我们的贪心无法解决下面的这种情况：
我们有4个小矮人，他们的身高和手臂长度分别是：
6 1
1 7
1 7
1 7
可知他们的能力大小分别是
7
8
8
8
我们假设坑的深度为10
所以按照贪心的思想，我们让能力小的站在最上面先出去
如图：
可知身高为6的这个小矮人，伸开胳膊长度是1 ，正好能爬出去。
剩下3个小矮人，最上面的那个伸开手臂总高度此时为3+7=10，也刚好能爬出去。
此时能出去的总人数为2
但是我们假如让身高为6的这个小矮人站在最下面，我们可以出去的人数为3。
可见，使用贪心的思想，浪费了身高高的这种小矮人。
这种小矮人有时候站在下面会更好。
那么我们怎么消除这种错误的站位呢？
现在我们知道了只按照能力大小排序是不对的。
那么我们又想不到正确的排序方式，那么我们就只能动态的来调整喽，就是DP的思想。
下面我先阐明一个事实：
假如我们一开始，将 n 个小矮人按照能力大小排序了。使用贪心的思想我们能出去 i 个小矮人。
那么我们剩下的 n-i 个小矮人能够代替任何一个已经出去的小矮人出去。
为什么呢？
因为下面的小矮人的能力更强啊，交换一下位置，这个能力更强的小矮人肯定也能出去。
由于我们 ！有可能 ！ 不想让上述那种特例里边，那个身高高的小矮人先出去，那么我们怎么办呢？
假如我们已经出去了 i 个小矮人，可知这 i 个小矮人任意调整出去的顺序都是可以的。
我们假如 第 i + 1 个小矮人出不去了，那么我们需要调整了。基于上面我阐述的事实可知，我们可以用第 i+1 个小矮人代替上面已经出去的 i 个小矮人种的任何一个。
那么我们是不是代替身高最高的那个最好？
因为把身高高的给替换下来，才有可能使坑能的高度更高，才有可能使更多的人出去。
如图：
可知此时出去的人数仍然为2，但是坑内剩余人的高度更高了，原来为2，现在为7.
就有可能有更多的人能爬出去了。
此时身高为6的这个小矮人虽然爬不上去，但是最下面那个身高为1的小矮人发现此时自己可以站到6的肩膀上爬出去了。
所以算法的设计思想就是，当我们按顺序爬不出去了，就想着用一个能力更强的但身高低的人去替换，上面已经出去了的 身高高，但能力低的人。
这样我们在保证出去的人数不减的情况下，使坑内剩余的高度更高了，那么我们再去看看坑内有没有人能出去。
直到我们无法使用能力更强但身高低的人去替换已经出去的能力弱但身高高的人的时候，这个时候就是最优解了。
按照上述写法，我写了一个比较复杂了，去在维护坑内剩余人的高度，然而wa了。。。
下面的解法中，每个人都只访问了一次。
每个人都先判断出去了 ans 个人后，我能不能作为第 ans+1 个人出去。
然后去调整自己的出去次序，前面所有人他都可以替代，去尽可能使坑内的高度更高。
但是，更新前面的 f 有什么帮助吗？？？
每次我们如果能使出去的人增大，肯定是使用 f[ans]+p[i].b 来计算的啊！
为啥我们不只是更新 f[ans] 呢？
因为我们是使用f[ans-1]+p[i].a来更新f[ans]的，这个人更新完，下一个人又要在这个基础上在次更新，所以我们不能只仅仅更新f[ans]。
f[i]就是递推的那个数组，用来记录前i个人，前ans个出去个人后坑内的最大高度。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
class P
{
public:
int a,b,sum;
};
bool operator < (const P &a,const P &b)
{
return a.sum<b.sum;
}
P p[maxn];
int n,H;
int f[maxn];
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&n))
{
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
scanf("%d %d",&p[i].a,&p[i].b);
p[i].sum=p[i].a+p[i].b;
f[0]+=p[i].a;
}
scanf("%d",&H);
sort(p+1,p+1+n);
int ans=0;
for(int i=1;i<=n;i++)
{
if(f[ans]+p[i].b>=H)
{
f[ans+1]=f[ans]-p[i].a;
ans++;
}
for(int j=ans-1;j>=0;j--)
{
f[j+1]=max(f[j+1],f[j]-p[i].a);
}
}
printf("%d\n",ans);
}
return 0;
} 叶子合并leaves
Description
在一个美丽的秋天，丽丽每天都经过的花园小巷落满了树叶，她决定把树叶堆成K堆，小巷是笔直的 共有N片树叶（树叶排列也是笔直的），每片树叶都有一个重量值，并且每两片想邻的树叶之间的距离都是1 现把所有的树叶按从左到右的顺序进行编号，编号为1…N。丽丽移动每片树叶所消耗能量等于这片树叶的重量 乘以移动的距离，丽丽决定分K天完成，每天堆一堆，并且规定只能把树叶往左移动，因为丽丽每天都是从右往左 经过小巷的。求丽丽完成任务所消耗的最少能量。
Input
输入的第一行为两个用空格隔开的正整数N和K。后面有N行 每行一个正整数表示叶子的重量（第i+1行表示第i片树叶的重量）
Output
输出为一个整数，表示把树叶堆成K堆所消耗的最少体力。
Sample Input 1
5 2
1
2
3
4
5
Sample Output 1
13
Hint
N在(0,1001)
K在(0,11)
这个题目一看就是DP嘛，因为我们不知道吧叶子堆在哪里好，1000片叶子直接枚举肯定不成。
那就去找状态转移方程吧。
可知我们的最终目的是要把 n 片树叶分成 k 份。
那么我们是不是可以先把前 i 片树叶分成 k - 1 份。
让后把第 i+1 片树叶到第 n 片 分成一份，这样总共就是k 份了。
我们枚举每一个可能的 i 的位置，找到最优的分解方式就好。
我们使用ans[ i ] [ j ]数组来表示我们把第 i 到第 j 片树叶合并到第 j 片树叶的代价。
dp[ i ] [ j ] 数组用来保存把前 i 个树叶分成 j 份的最小代价
状态转移方程：
dp [ i ] [ j ] = min{
dp( i-1, kk - 1) + ans[ i ][ i ]
dp( i-2, kk - 1) + ans[ i-1 ][ i ]
dp( i-3, kk - 1) + ans[ i -2 ][ i ]
…
}
对于我们的样例来说就是这样。
我们把前1个叶子分成 1 份好呢？
还是把前2个叶子分成 1 份好呢？
还是把前3个叶子分成 1 份好呢？
还是把前4个叶子分成 1 份好呢？
最后把最优的答案存入dp [ 5 ] [ 2 ]
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1001;
int a[maxn];
int sum[maxn];
int ans[maxn][maxn];
int dp[maxn][maxn];
int n, k;
//计算把前 nn 个树叶 分成kk份的最小花费
int calc(int nn, int kk)
{
//使用记忆优化， 如果之前已经计算过了，那么把答案直接返回
if (dp[nn][kk] != inf)return dp[nn][kk];
//如果只分一份，那么就是直接把 i到j 之间的树叶都移动到j的花费
if(kk==1)return ans[1][nn];
//否则枚举 把前面分成k-1份的分发。找到最优解
for (int i = kk - 1; i < nn; i++)
{
dp[nn][kk] = min(dp[nn][kk], calc(i, kk - 1) + ans[i + 1][nn]);
}
return dp[nn][kk];
}
int main()
{
while (~scanf("%d %d", &n, &k))
{
memset(dp, 0x3f, sizeof(dp));
memset(sum, 0, sizeof(sum));
memset(a, 0, sizeof(a));
//由于题目中树叶的顺序是逆序的，我们先倒着输进来
for (int i = n; i >= 1; i--)
{
//dp[i][i]表示把i个树叶分成i份，那么可知不用动，所以花费为0
dp[i][i] = 0;
scanf("%d", &a[i]);
}
//计算一下前缀和，因为我们需要指导第i片树叶到第j片树叶的重量和
for(int i=1;i<=n;i++)
{
sum[i] = sum[i - 1] + a[i];
}
//计算一下把第i个到第j个树叶堆到第j个树叶的花费
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
//可知把第i个到第j个树叶堆到第j个树叶的花费
//等于把第i个到第j-1个树叶堆到第j-1个树叶的花费 加上 把这些树叶从第j-1个树叶的位置
//移动到第j个树叶的位置
ans[i][j] = ans[i][j - 1] + sum[j - 1] - sum[i - 1];
}
}
//计算一下把n 个树叶 分成 k 份的代价
calc(n, k);
printf("%d\n", dp[n][k]);
}
return 0;
} problem a
Description
一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)
Input
第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi
Output
一个整数，表示最少有几个人说谎
Sample Input 1
3
2 0
0 2
2 2
Sample Output 1
1
分析：
每个人给的那两个数字其实可以转化为，一个名次区间。
明显不符合的直接去掉。
重复的记录权重，权重不得超过名次区间长度。
最后求最多不相交的区间个数（带权重）。
这就成了背包问题了。
#include<map>
#include<string.h>
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 100001;
int n;
class P
{
public:
int s, e;
P(int ss = 0, int ee = 0)
{
s = ss; e = ee;
}
};
bool operator < (const P& a, const P& b)
{
if (a.s == b.s)return a.e < b.e;
return a.s < b.s;
}
P p[maxn];
int cnt = 0;
map<P, int> map1;
int a, b;
int dp[maxn];
//如果我们想要t这个区间，那么前边与我们这个t区间不相交的区间个数的最大值是多少？
int find(int t)
{
for (int i = t - 1; i >= 1; i--)
{
//找到第一个与我们不相交的区间，让后返回结果
if (p[i].e < p[t].s)return dp[i];
}
//如果没找到，说明前边的区间都会与我相交，那么我要t这个区间，对多的答案就是0+自己的权重
return 0;
}
int main()
{
while (~scanf("%d", &n))
{
cnt = 1;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &a, &b);
if (a + b >= n)continue;
P t;
t.s = a + 1;
t.e = n - b;
//储存区间，不得重复
if (map1[t] == 0)
{
p[cnt++] = t;
}
//记录权重
map1[t]++;
map1[t] = min(map1[t], t.e - t.s + 1);
}
//排序
sort(p + 1, p + cnt);
for (int i = 1; i <= cnt; i++)
{
//转态转移
dp[i] = max(dp[i - 1], find(i) + map1[p[i]]);
}
printf("%d\n", n-dp[cnt]);
}
return 0;
} Disease Manangement 疾病管理
Description
Alas! A set of D (1 <= D <= 15) diseases (numbered 1…D) is running through the farm. Farmer John would like to milk as many of his N (1 <= N <= 1,000) cows as possible. If the milked cows carry more than K (1 <= K <= D) different diseases among them, then the milk will be too contaminated and will have to be discarded in its entirety. Please help determine the largest number of cows FJ can milk without having to discard the milk.
Input
- Line 1: Three space-separated integers: N, D, and K * Lines 2…N+1: Line i+1 describes the diseases of cow i with a list of 1 or more space-separated integers. The first integer, d_i, is the count of cow i’s diseases; the next d_i integers enumerate the actual diseases. Of course, the list is empty if d_i is 0. 有N头牛,它们可能患有D种病,现在从这些牛中选出若干头来,但选出来的牛患病的集合中不过超过K种病.
Output
- Line 1: M, the maximum number of cows which can be milked.
Sample Input 1
6 3 2
0———第一头牛患0种病
1 1——第二头牛患一种病,为第一种病.
1 2
1 3
2 2 1
2 2 1
Sample Output 1
5
OUTPUT DETAILS:
If FJ milks cows 1, 2, 3, 5, and 6, then the milk will have only two
diseases (#1 and #2), which is no greater than K (2).
分析：
大佬们都说是状压DP。
emmmmmm，他的确是个状压DP。。。
我们其实也枚举了每一种生病的情况，但好在我们算的比较快。
我们也是把牛的病转化成二进制表示
有d种病，那么病的所有组合就有cnt=(1<<d)-1种
当我们输入到一头牛时，我们把这头牛所有可能带来的，疾病集合的结果都更新一下，
但要注意，我们得从cnt — 0 这样来更新。
为什么呢？
因为如果从0 — cnt 那么我们这头带来的更新效果在不断往后传递。
导致一头牛在集合中不断起作用。致使答案错误。
比如：
一头牛的病的二进制表示为 0001
这头牛与集合f[0000] 合并 成为0001，
那么我们更新 f[0001]=max(f[0001],f[0000]+1)
在更新f[0001]时，我们又能加入这头牛 0001 生成 0001
更新f[0001]=max(f[0001],f[0001]+1)
但其实这头牛在0000这个状态时，已经更新过f[0001]了，现在又更新，导致重复。
所有要从后往前更新，这样就巧妙的避免了重复更新，因为合并出来的值指只会更大，这样当前遍历的集合状态的时候能保证，当前牛还没有作用过当前集合，就不会产生一头牛重复作用在一个集合上的这种问题了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1001;
int n,d,k,t,tt;
int a[maxn];
int f[(1<<16)-1];
bool check(int t)
{
int cnt=0;
while(t)cnt++,t-=t&-t;
return cnt<=k;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d %d %d",&n,&d,&k))
{
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
int cnt=(1<<d)-1;
for(int i=1;i<=n;i++)
{
scanf("%d",&t);
for(int j=0;j!=t;j++)
{
scanf("%d",&tt);
a[i]|=(1<<(tt-1));
}
for(int j=cnt;j>=0;j--)
{
int t=j|a[i];
f[t]=max(f[t],f[j]+1);
}
}
int ans=0;
for(int i=0;i<=cnt;i++)
{
if(check(i))
{
ans=max(ans,f[i]);
}
}
printf("%d\n",ans);
}
return 0;
}
不会做，老办法，找大佬的代码打注释：
感谢：http://hzwer.com/2819.html
设计到预处理，储存优化，递推DP，广搜
其实还是比较简单的。虽然有点复杂。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,cnt,a,b;
int head[1001],d[1001],q[1001];
int dis[1001][1001],p[1001][1001];
double f[1001][1001];
struct data{int to,next;}e[1001];
//这个加边时，同时也加了反向边，可知所有边都存在e数组中了。
//偶数边是正向边，奇数边为反向边。
//to是到达到的下一个节点是谁
//next表示，从U出去的边的上一条边是谁
//d用来记录从U出去的边的个数
void insert(int u,int v)
{
cnt++;e[cnt]=data{v,head[u]};head[u]=cnt;d[u]++;
cnt++;e[cnt]=data{u,head[v]};head[v]=cnt;d[v]++;
}
//计算从x到y的平均步数，就是假设现在聪聪在x，可可在y，我们计算聪聪到可可的平均步数
double dp(int x,int y)
{
//如果这个答案已经被算过了，我们就直接返回答案
if(f[x][y])return f[x][y];
//如果当前聪聪和可可在一起站着，可知不需要步数，直接为0
if(x==y)return 0;
//如果聪聪下一步或者下下一步就是可可的位置，那么再来一步就能追上可可。因为聪聪先走
if(p[x][y]==y||p[p[x][y]][y]==y)return f[x][y]=1;
//如果不是上述三种情况，那么我们计算出来，聪聪走两步后的位置，
//递归使用dp(聪聪走两步后的位置，可可的位置) 来计算当可可这一步不动时，聪聪追上可可的平均步数
double tot=dp(p[p[x][y]][y],y);
//让后，加上聪聪跑到其他相邻节点时，聪聪追上可可的平均步数
//遍历所有y相邻的边
for(int i=head[y];i;i=e[i].next)
tot+=dp(p[p[x][y]][y],e[i].to);
//记录病返回结果
return f[x][y]=tot/(d[y]+1)+1;
}
//使用bfs来预处理出，聪聪和可可在每种位置下，聪聪的下一步怎么走，存入p数组
//p[i][j]就表示，当聪聪在i这个节点，可可在j这个节点时，聪聪下一步应该去哪里
void bfs(int x)
{
int t=0,w=1;
//q[0] 存第一个点
//初始化dis
q[0]=x;dis[x][x]=0;
while(t!=w)
{
//now表示当前队列里边第一个人
//tmp表示从起点到当前节点的下一个节点
//t++表示队列弹出一个元素
int now=q[t],tmp=p[x][now];t++;
//实现循环队列
if(t==1001)t=0;
//遍历所有now连接的边
for(int i=head[now];i;i=e[i].next)
{
//如果从x到这条边的下一个点没有路，或者通过当前节点到达目的节点的距离等于直接到达目的
//节点的距离并且，当前节点的序号比较小，那么我们更新距离，更新数组p，往队列里添加下一层
if(dis[x][e[i].to]==-1||(1+dis[x][now]==dis[x][e[i].to]&&tmp<p[x][e[i].to]))
{
dis[x][e[i].to]=dis[x][now]+1;
p[x][e[i].to]=tmp;
if(!tmp)p[x][e[i].to]=e[i].to;
q[w]=e[i].to;
w++;
//实现循环队列
if(w==1001)w=0;
}
}
}
}
int main()
{
memset(dis,-1,sizeof(dis));
//n个点，m条边
scanf("%d%d",&n,&m);
//a为聪聪，b为可可
scanf("%d%d",&a,&b);
for(int i=1;i<=m;i++)
{
int u,v;scanf("%d%d",&u,&v);
//加边
insert(u,v);
}
//从每一个点bfs出去
for(int i=1;i<=n;i++)bfs(i);
//输出从a到b的平均步数
printf("%.3lf",dp(a,b));
return 0;
} 其中上述大佬代码中的dis其实利用率并不高。
dis的作用就是为了让我们判断这个点是不是更远。
只有我们当前now这个点比，e[ i ].to 距离x近我们才会考虑是否更新p[x][e[i].to]
然而我们可以使用广搜的特性，一层一层的搜索，记录层次就好，不需要dis
我的代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2002;
class R
{
public:
int v,next;
};
R e[maxn];
int total;
int head[maxn];
int start,endd;
int N,E;
int u,v;
int p[maxn][maxn];
double f[maxn][maxn];
int d[maxn];
bool vis[maxn];
int layer[maxn];
void add()
{
e[total]={v,head[u]};head[u]=total++;d[u]++;
e[total]={u,head[v]};head[v]=total++;d[v]++;
}
double dp(int ss,int ee)
{
if(f[ss][ee])return f[ss][ee];
if(ss==ee)return f[ss][ee]=0;
if(p[ss][ee]==ee||p[p[ss][ee]][ee]==ee)return f[ss][ee]=1;
int ppp = p[p[ss][ee]][ee];
double sum=dp(ppp,ee)+1;
for(int i=head[ee];i;i=e[i].next)
{
int vv=e[i].v;
sum+=dp(ppp,vv)+1;
}
return f[ss][ee]=sum/(d[ee]+1);
}
void bfs(int x)
{
queue<int> q[2];
memset(layer,0,sizeof(layer));
int pre=0,nextt=1;
layer[x]=1;
p[x][x]=x;
for(int i=head[x];i;i=e[i].next)
{
int vv=e[i].v;
p[x][vv]=vv;
layer[vv]=layer[x]+1;
q[pre].push(vv);
}
while(q[0].size()||q[1].size())
{
while(q[pre].size())
{
int pp=q[pre].front();
q[pre].pop();
for(int i=head[pp];i;i=e[i].next)
{
int vv=e[i].v;
if(!layer[vv]||(layer[pp]<layer[vv]&&p[x][pp]<p[x][vv]))
{
q[nextt].push(vv);
p[x][vv]=p[x][pp];
layer[vv]=layer[pp]+1;
}
}
}
swap(pre,nextt);
}
}
int main()
{
while(~scanf("%d %d %d %d",&N,&E,&start,&endd))
{
memset(head,0,sizeof(head));
memset(p,0,sizeof(p));
memset(d,0,sizeof(d));
total=1;
for(int i=0;i!=E;i++)
{
scanf("%d %d",&u,&v);
add();
}
for(int i=1;i<=N;i++)
{
bfs(i);
}
printf("%.3f\n",dp(start,endd));
}
return 0;
} 跑的速度比大佬的代码要慢了近一倍
就差在那个循环队列上。。。
消失之物
Description
ftiasch 有N个物品, 体积分别是W1,W2, …,WN。 由于她的疏忽, 第i个物品丢失了。 “要使用剩下的N– 1 物品装满容积为x的背包，有几种方法呢？” — 这是经典的问题了。她把答案记为Count(i, x)，想要得到所有1 <= i <= N, 1 <= x <= M的Count(i, x)表格。
Input
第1行：两个整数N(1 ≤N≤ 2 × 103) 和M(1 ≤M≤ 2 × 103)，物品的数量和最大的容积。
第2行：N个整数W1,W2, …,WN, 物品的体积。
Output
一个N×M的矩阵，Count(i, x)的末位数字。
Sample Input 1
3 2
1 1 2
Sample Output 1
11
11
21
Hint
如果物品3丢失的话，只有一种方法装满容量是2的背包，即选择物品1和物品2。
嗯，是个完全背包问题。
让每个物品都先作用上去，然后再删去丢失的哪个物品的效果。
输出。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
int n,m;
int a[maxn];
int dp[maxn],ans[maxn];
int main()
{
while(~scanf("%d %d",&n,&m))
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
dp[j]+=dp[j-a[i]];
dp[j]%=10;
}
}
for(int i=1;i<=n;i++)
{
memcpy(ans,dp,sizeof(dp));
for(int j=a[i];j<=m;j++)
{
ans[j]-=ans[j-a[i]];
if(ans[j]<0)ans[j]+=10;
}
for(int j=1;j<=m;j++)
{
printf("%d",ans[j]);
}
printf("\n");
}
}
return 0;
}
京公网安备 11010502036488号