Zut_round 6

A. 클래식 LIS 템 플 릿 (poj 2533)
제목: 최 장 엄격 한 상승 서브 시퀀스 구하 기

#include
#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=1e3+9;
#define line '
'
#define gt getchar()
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
int a[N],dp[N];
int main()
{
	int n=read();for(int i=1;i<=n;++i)a[i]=read(),dp[i]=1;
	int ans=1;
	for(int i=2;i<=n;++i){
		for(int j=1;j<i;++j)
			if(a[j]<a[i])dp[i]=max(dp[j]+1,dp[i]);
		ans=max(ans,dp[i]);
	}
	cout<<ans<<line;
	return 0;
}

B. 다단 계 의사 결정 dp 템 플 릿 (hdu 2059)
제목: L 길이 의 트랙 에서 거북 이 는 전차 에 전기 가 있 을 때 속도 x, y 가 항정 속도 v 의 토끼 보다 먼저 종점 에 도착 할 수 있 습 니까? 트랙 에 n 개의 속성 이 있 는 충전소 가 있 습 니 다.
사고: 같은 거리 에서 시간 을 비교 하고 dp [i] 를 제 j (ji) 로 정의 합 니 다.

#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=1e2+9;
#define line '
'
#define gt getchar()
#define mid ((L+R)>>1)
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
double L,a[N],dp[N];
int main()
{
    int n,s,t,v,x,y;
    while(cin>>L){
        cin>>n>>s>>t>>v>>x>>y;
        for(int i=1;i<=n;++i)a[i]=read(),dp[i]=INT_MAX;
        a[n+1]=L;dp[0]=0;dp[n+1]=INT_MAX;
        for(int i=1;i<=n+1;++i)for(int j=0;j<i;++j){
            double mx=0;
            if(a[i]-a[j]>s)mx=(a[i]-a[j]-s)/y+s*1.0/x;
            else mx=(a[i]-a[j])/x;
            mx+=dp[j];
            if(j)mx+=t;
            dp[i]=min(dp[i],mx);
        }
        if(dp[n+1]<L/v)cout<<"What a pity rabbit!"<<line;
        else cout<<"Good job,rabbit!"<<line;
    }
    return 0;
}

C、CodeForces - 1077A
제목: k 차 조작, a 감 b 를 추가 하여 순서대로 진행 하고 마지막 결 과 를 묻는다.

#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=1e3+9;
#define line '
'
#define gt getchar()
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
int main()
{
	int T=read();
	while(T--){
		LL a=read(),b=read(),k=read();
		LL ans=k/2*(a-b);
		if(k&1)ans+=a;
		cout<<ans<<line;
	}
	return 0;
}

D、CodeForces - 1077B
제목: 각 아파트 의 불 은 0, 1 두 가지 상태 이 고 101 형 아 파 트 는 방 해 를 받 을 수 있 으 며 최소 불 을 끄 는 개 수 를 구하 여 각 아파트 가 방 해 를 받 지 않도록 한다.
사고: 실제 적 으로 10101 과 101 이 몇 개 있 는 지 찾 는 것 이다. 최소 불 끄 는 횟수 는 모두 1 이 고 다른 예 를 들 어 1010101, 101010101 등 은 모두 이 두 가지 상황 으로 전환 할 수 있 으 며 통 계 를 하면 된다.

#include
#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=1e2+9;
#define line '
'
#define gt getchar()
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
int main()
{
	string str="";int a;
	int n=read();for(int i=1;i<=n;++i)a=read(),str+='0'+a;
	str+="000000";int i=0,ans=0;
	while(i<=n){
		if(str.substr(i,5)=="10101")ans++,i+=4;
		else if(str.substr(i,3)=="101")ans++,i+=2;
		else i++;
	}
	cout<<ans<<line;
	return 0;
}

E、CodeForces - 1077C
제목: n 개 수 에서 어떤 수 를 삭제 할 수 있 는 지 판단 하여 나머지 수의 한 수 를 다른 모든 수의 합 으로 만 듭 니 다.
사고: 기록 총화, 순환 은 이 수 를 삭제 하 는 것 이 조건 을 만족 시 킬 수 있 는 지 를 순서대로 판단 한다.

#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=2e5+9;
#define line '
'
#define gt getchar()
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
LL sum,a[N];
unordered_map<LL,int> mp;
int main()
{
	int n=read();for(int i=1;i<=n;++i)a[i]=read(),sum+=a[i],mp[a[i]]++;
	vector<int> V;
	for(int i=1;i<=n;++i){
		mp[a[i]]--;
		LL t=sum-a[i];
		if(!(t&1)&&mp[t/2])V.push_back(i);
		mp[a[i]]++;
	}
	cout<<V.size()<<line;
	for(auto it:V)cout<<it<<" ";
	cout<<line;
	return 0;
}

F、CodeForces - 1077D
제목: n 개 수 중에서 k 개 수 를 선택 하여 이 k 개 수 를 n 개 수의 중복 횟수 에서 가장 많은 사고 방향 으로 한다. 중복 횟수 가 가장 많 고 직접 2 분 중복 횟수 로 이때 중복 횟수 를 만족 시 키 는 개수 가 k 개 보다 클 수 있 는 지 판단 한다.

#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=2e5+9;
#define line '
'
#define gt getchar()
#define mid ((L+R)>>1)
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
unordered_map<int,int> mp;
int n,k,x;
bool judge(int t)
{
	int num=0;
	for(auto it:mp)num+=it.second/t;
	return num>=k;
}
int main()
{
	n=read(),k=read();for(int i=1;i<=n;++i)x=read(),mp[x]++;
	int L=1,R=n,ans;
	while(L<=R){
		if(judge(mid)){
			ans=mid;
			L=mid+1;
		}
		else R=mid-1;
	}
	for(auto it:mp){
		if(k==0)break;
		int y=min(k,it.second/ans);
		k-=y;
		while(y--)cout<<it.first<<" ";
	}
	cout<<line;
	return 0;
}

G、CodeForces - 1077E
제목: 정의 서열 F: (x, 2x, 4x.. 곶 길이 n 인 배열 a, a [i] 가 나타 난 횟수 에 따라 서열 F 의 서열 과
사고: a [i] 범위 가 1e9 에 달 하지만 각 a [i] 의 등장 횟수 는 n 이 가장 많 고 F 서열 의 첫 번 째 항목 을 선택 하여 2 점 을 할 수 있다.

#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=2e5+9;
#define line '
'
#define gt getchar()
#define mid ((L+R)>>1)
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
map<int,int> mp;
int a[N];
int main()
{
	int n=read(),x;for(int i=1;i<=n;++i)x=read(),mp[x]++;
	int k=0,m=0;LL ans=0;
	for(auto it:mp)a[++k]=it.second,m=max(m,a[k]);
	sort(a+1,a+k+1);
	for(int i=1;i<=m;++i){
		int t=i,L=1;
		LL sum=0;
		while(1){
			L=lower_bound(a+L,a+k+1,t)-a;
			if(L>k)break;
			L++;
			sum+=t;
			t<<=1;
		}
		ans=max(ans,sum);
	}
	cout<<ans<<line;
	return 0;
}

H、CodeForces - 1077F1
제목: n 개 수 중 x 개 수의 최대 합 을 선택 하 십시오. 그러나 임의의 연속 k 개 수 중 선택 한 것 이 있어 야 합 니 다.
사고: dp [i] [j] 를 앞의 i 개 수 에서 j 개 를 선택 하 는 최대 치 로 정의 합 니 다. 그 중에서 i 개 는 반드시 선택 하고 k 의 제한 이 있 기 때문에 마지막 k 개 수 는 반드시 선택 이 있어 야 합 법화 전이 방정식 dp [i] [j] = max (dp [i] [j], dp [p] [j - 1] + a [i]) 중 max (0, i - k) < = p

#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=2e2+9;
#define line '
'
#define gt getchar()
#define mid ((L+R)>>1)
#define inf 0x3f3f3f3f3f3f3f3f
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
LL dp[N][N],a[N]; 
int main()
{
	int n=read(),k=read(),x=read();
	for(int i=1;i<=n;++i)a[i]=read();
	LL ans=-1;memset(dp,-inf,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;++i)for(int j=1;j<=x;++j)for(int p=max(0,i-k);p<i;++p)
		dp[i][j]=max(dp[i][j],dp[p][j-1]+a[i]);
	for(int i=n-k+1;i<=n;++i)ans=max(ans,dp[i][x]);
	cout<<ans<<line;
    return 0;
}

I、CodeForces - 1077F2
单调队列维护dp[p][j-1]单增

#include
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int N=5e3+9;
#define line '
'
#define gt getchar()
#define mid ((L+R)>>1)
#define inf 0x3f3f3f3f3f3f3f3f
int read(){int x=0,op=1;char c=gt;while(!isdigit(c)){if(c=='-')op=-1;c=gt;}while(isdigit(c))x=x*10+c-48,c=gt;return x*op;}
LL dp[N][N],a[N],Q[N],que[N];
int main()
{
	int n=read(),k=read(),x=read();
	for(int i=1;i<=n;++i)a[i]=read();
	LL ans=-1;memset(dp,-inf,sizeof(dp));
	dp[0][0]=0;
	for(int j=1;j<=x;++j){
		int L=0,R=1;Q[0]=0;
		for(int i=1;i<=n;++i){
			while(L<R&&Q[L]<i-k)L++;
			dp[i][j]=dp[Q[L]][j-1]+a[i];
			while(L<R&&dp[i][j-1]>=dp[Q[R-1]][j-1])R--;
			Q[R++]=i;
		}
	}
	for(int i=n-k+1;i<=n;++i)ans=max(ans,dp[i][x]);
	cout<<ans<<line;
    return 0;
}