Nothing to fear
种一棵树最好的时间是十年前，其次是现在！
那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~
2020.5.7
人一我十， 人十我百，追逐青春的梦想，怀着自信的心，永不言弃！
one
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 105;
const int MAX = 2147483647;
int f[N][N];
struct node{
int h , w;
}a[N];
bool cmp(node x,node y)
{
return x.h < y.h;
}
void slove()
{
int n , m;
cin >> n >> m;
m = n - m;
for(int i = 1;i <= n ;i ++)
{
cin >> a[i].h >> a[i].w;
}
sort(a + 1,a + 1 + n,cmp);
for(int i = 2;i <= n; ++i)
for(int j = 2 ;j <= min(i , m); ++j)
{
f[i][j] = MAX;
for(int k = j - 1; k < i; ++k)
f[i][j] = min(f[i][j],f[k][j-1] + abs(a[i].w-a[k].w));
}
int ans = MAX;
for(int i = m;i <= n; ++i) ans = min(ans,f[i][m]);
printf("%d",ans);
}
int main()
{
slove();
return 0;
}
two
f[i] 表示前 i 个人需要的教室的最少的个数
一共会遇到两种情况:
- 连续都是喜欢一个人
- 两个喜欢的人数差 <= m
遇到这两种情况:
f[i] = min(f[i],f[j] + 1);
关键在于 如何找到前面的 状态表示
利用前缀和记录一段区间内连续 1 的喜欢人数 和 2的喜欢人数 可以降低时间复杂度
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2505;
const int MAX = 0x3f;
int a[N];
int s[3][N];
int f[N];
int Sum(int x , int y)
{
return (s[1][y] - s[1][x]) - (s[2][y] - s[2][x]);
}
int main()
{
int n , m;
cin >> n >> m;
memset(f , MAX , sizeof f);
for(int i = 1;i <= n ;i ++)
{
scanf("%d",&a[i]);
if(a[i] == 1)s[1][i] = s[1][i-1] + 1,s[2][i] = s[2][i-1];
else s[2][i] = s[2][i-1] + 1,s[1][i] = s[1][i-1];
}
f[0] = 0,f[1] = 1;
for(int i = 1;i <= n ;i ++)
{
for(int j = 0;j < i ;j ++)
{
if(abs(Sum(j,i)) <= m || s[1][i] - s[1][j] == 0 ||
s[2][i] - s[2][j] == 0)
{
f[i] = min(f[i],f[j] + 1);
}
}
}
cout << f[n] << endl;
return 0;
}
three
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <cmath>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;
void slove()
{
int n;
cin >> n;
vector<int> a(n + 1,0),b(n + 1,0);
for(int i = 1;i <= n ;i ++)
{
cin >> a[i] >> b[i];
}
for(int i = 1;i <= n ;i ++)
{
if((a[i] - a[i-1]) >= (b[i]-b[i-1]) && a[i] >= a[i-1] && b[i] >= b[i-1] && a[i] >= b[i])
continue;
else {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
int main()
{
#ifdef LOCAL
auto start_time = clock();
cerr << setprecision(3) << fixed;
#endif
SIS;
cin >> t;
while(t--)
{
slove();
}
#ifdef LOCAL
auto end_time = clock();
cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms
";
#endif
}