[数据结构与算法]22.2.6

一.

算法学习;

1.区间dp

?eg:石子合并;

#include<bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a)	for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using ll=long long ;
using namespace std;
const int N=307;
int a[N],s[N];
int f[N][N];
int main()
{	
	int n;
	cin>>n;
	rep2(i,1,n){
		scanf("%d",&a[i]);
		s[i]+=s[i-1]+a[i];求前缀和,因为对于某个区间的代价的计算,用前缀和方便快捷;
	}
	rep2(len,1,n-1){区间长度,最长是n-1;
		for(int i=1;i+len<=n;i++){i是区间左端点,右端点i+len要<=n(要符合实际)
			int j=i+len;j是右端点
			f[i][j]=INT_MAX;初始化
			for(int k=i;k<j;k++){枚举分割点;记住k<j!!;或者写k<=j-1;记住!
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
			}
		}
	}
	cout<<f[1][n];
	return 0;		 
}

2.贪心-区间选点；

?①结构体内嵌比较函数，实现比在在外部用sort＋另写一个排序函数省时省力

(4条消息) C/C++对bool operator < (const p &a)const的认识，运算符重载详解(杂谈)_weixin_34023863的博客-CSDN博客https://blog.csdn.net/weixin_34023863/article/details/85886339?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_paycolumn_v3&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_paycolumn_v3&utm_relevant_index=2

#include<bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a)	for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using ll=long long ;
using namespace std;
const int N = 100010;
int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];
int main()
{
    scanf("%d", &n);
    rep1(i,0,n) scanf("%d%d", &range[i].l, &range[i].r);
    sort(range, range + n);
    int res = 0, ed = -2e9;
    rep1(i,0,n)
        if (ed < range[i].l)
        {
            res ++ ;
            ed = range[i].r;
        }
    printf("%d\n", res);
    return 0;
}

?

二.oj训练赛

1.向上取整的做法，判断余数；

2.?Okabe and Boxes

每次消除时考虑排序；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a)	for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using ll=long long ;
using namespace std;
const int N=3e5+10;
char s[100];
int a[N];
int top=0,ans=0;
int main()
{	
	int n,num=0;
	cin>>n;
	rep2(i,1,2*n){
	scanf("%s",&s);	
	if(s[0]=='a'){
		int x;
		scanf("%d",&x);
		a[++top]=x;
	}
	else {
	num++;
	if(top==0)continue;
	if(a[top]!=num){
		top=0;
		ans++;
	}
	else top--;	
	}
	}
	cout<<ans;
	
	return 0;		 
}