학교 숙제-dp연습

제목.
★Stringsobits01열은 정렬된 N(N<=31)자리 2진수를 고려합니다.너는 이것이 매우 재미있다는 것을 알게 될 것이다.그들은 배열되어 있고 모든 가능한 길이가 N이고 1이 포함된 개수는 L(L<=N)과 같은 개수보다 작기 때문이다.당신의 임무는 I (1 < = I < = N 길이의 이진수 개수) 를 출력하는 것입니다. 길이는 N 이고, 1의 개수는 L과 같은 이진수보다 작습니다.PROGRAM NAME: Kimbits INPUT FORMAT, 공백으로 세 개의 정수 N, L, I. SAMPLE INPUT(file kimbits.in) 5 3 19 OUTPUT FORMAT
조건을 충족시키는 큰 이진수를 출력하는 한 줄입니다. 
SAMPLE OUTPUT (file kimbits.out)  10011 
문제풀이
이 문제는 한 명 한 명 시험이라고 생각합니다. 만약에 현재 0을 채우면 조합수로 모두 몇 개의 숫자가 있는지 계산하고 i보다 작으면 현재 1을 채우고 그렇지 않으면 0을 채우고 계속 시험해 보면 됩니다.얘가 디지털 DP가 될 것 같은데?QAQ를 잘 생각을 못했어요.
 
코드
 

/*Author:WNJXYK*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<set>

using namespace std;



#define LL long long



inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}

inline void swap(LL &x,LL &y){LL tmp=x;x=y;y=tmp;}

inline int remin(int a,int b){if (a<b) return a;return b;}

inline int remax(int a,int b){if (a>b) return a;return b;}

inline LL remin(LL a,LL b){if (a<b) return a;return b;}

inline LL remax(LL a,LL b){if (a>b) return a;return b;}



LL n,l,m;

int Ans[40];

LL Pow[32];

inline LL getC(int n,int m){

	LL Ans=1;

	if (n-m>m) m=n-m;

	for (int i=m+1;i<=n;i++) Ans*=i;

	for (int i=2;i<=n-m;i++) Ans/=i;

	return Ans;

}

inline LL getCS(int n,int m){

	LL Ans=1;

	for (int i=1;i<=m;i++) Ans+=getC(n,i);

	return Ans;

}

int main(){

	scanf("%lld%lld%lld",&n,&l,&m);

	for (int i=n;i>=2;i--){

		LL tmp=getCS(i-1,remin(i-1,(int)l));

		if (tmp<m){

			m-=tmp;

			Ans[i]=1;

			l-=1;

		}else{

			Ans[i]=0;

		}

	}

	Ans[1]=!(m==1);

	bool isOne=false;

	for (int i=n;i>=1;i--){

		isOne=isOne||Ans[i];

		if (isOne) printf("%d",Ans[i]);

	}

	printf("
");

	return 0;

}

 
 
제목.
★ Raucous Rockers'징을 깨는 록'밴드 당신은 방금 유행하는'징을 깨는 록'밴드가 녹음한 아직 발표되지 않은 N(1<=N<=20)곡의 판권을 계승했습니다.너는 그중에서 몇 곡의 노래를 정선해서 M(1<=M<=20)장의 CD를 발매할 계획이다.각 CD는 최대 T(1<=T<=20)분의 음악을 수용할 수 있으며, 한 곡은 두 장의 CD에 나누어 담을 수 없다.공교롭게도 너는 고전 음악광이어서 이 노래들의 예술적 가치를 어떻게 판정하는지 모른다.그래서 당신은 다음과 같은 기준에 따라 선택하기로 결정했습니다. 노래는 반드시 창작의 시간 순서에 따라 CD판에 나와야 합니다.선택한 노래의 수가 가능한 한 많다.PROGRAM NAME: rockers INPUT FORMAT 첫 번째 줄: 세 개의 정수: N, T, M. 두 번째 줄: N개의 정수, 각각 노래의 길이를 표시하고 창작 시간 순서에 따라 배열한다.SAMPLE INPUT(file rockers.in) 4 5 2 4 3 4 2 OUTPUT FORMAT는 M장의 CD판에 담을 수 있는 곡의 최대 수를 나타내는 정수이다.  SAMPLE OUTPUT (file rockers.out)  3 
문제풀이
이 문제는 내가 오랫동안 조정했기 때문에 QAQ를 스스로 검토했다. 너무 졸려서 [귀신이 너를 믿는구나! 그래, f[i][j]={a,b}는 앞의 i곡에 j곡을 넣었는데 적어도 a곡의 시디가 필요했다. 그리고 그런 상황에서 마지막 시디는 b분 남았다.이렇게 f[i-1][j]와 f[i-1][j-1]에서 마음대로 옮기면 돼!
 
코드
 

/*Author:WNJXYK*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<set>

using namespace std;



#define LL long long



inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}

inline void swap(LL &x,LL &y){LL tmp=x;x=y;y=tmp;}

inline int remin(int a,int b){if (a<b) return a;return b;}

inline int remax(int a,int b){if (a>b) return a;return b;}

inline LL remin(LL a,LL b){if (a<b) return a;return b;}

inline LL remax(LL a,LL b){if (a>b) return a;return b;}



int n,t,m;

int ti[25];

struct Node{

	int index;

	int left;

	Node(){index=left=2147483647;}

	Node(int a,int b){index=a;left=b;};

	void update(Node x){

		int i=x.index;

		int l=x.left;

		if (i<index){

			index=i;

			left=l;

		}else if (i==index && l<left){

			left=l;

		}

	}

	void update_new(Node x,int xt){

		update(Node(x.index+1,t-xt));

		if (x.left-xt>=0) update(Node(x.index,x.left-xt));

	}

};

Node f[25][25];



int main(){

	scanf("%d%d%d",&n,&t,&m);

	for (int i=1;i<=n;i++) scanf("%d",&ti[i]);

	f[0][0].index=0;

	f[0][0].left=t;

	int min=2147483647;

	for (int i=1;i<=n;i++){

		for (int j=1;j<=i;j++){

			f[i][j].update(f[i-1][j]);

			f[i][j].update_new(f[i-1][j-1],ti[j]);

		}

	}

	int Ans=0;

	for (int i=1;i<=n;i++)if (f[n][i].index<=m) Ans=i;

	printf("%d
",Ans);

	return 0;

}

 
 
제목.
★Canada Tour 캐나다를 주유하여 항공사에서 개최하는 시합을 이겼습니다. 상품은 캐나다 투어 비행기표입니다.이 항공사가 개방한 가장 서쪽 도시에서 여행을 시작한 후에 서쪽에서 동쪽으로 여행해서 당신이 가장 동쪽 도시에 도착할 때까지 동쪽에서 서쪽으로 돌아오고 당신이 시작한 도시로 돌아갈 때까지 계속 여행하세요.모든 도시는 한 번만 방문할 수 있다. 여행이 시작된 도시를 제외하고 이 도시는 반드시 두 번 방문해야 한다(여행의 시작과 끝에).너는 다른 회사의 항로를 사용하거나 다른 교통수단을 사용하는 것을 허락하지 않는다.이 항공사가 개방한 도시의 목록과 두 도시 사이의 직항 노선의 목록을 보여 주십시오.가능한 한 많은 도시를 방문할 수 있는 노선을 찾아라. 이 노선은 반드시 상술한 조건을 만족시켜야 한다. 즉, 목록의 첫 번째 도시에서 여행을 시작하고 목록의 마지막 도시를 방문한 후에 첫 번째 도시로 돌아가야 한다.PROGRAM NAME: tour INPUT FORMAT Line 1: 항공사가 개방한 도시수 N과 열거할 직항로의 수량 V.N은 100보다 크지 않다
양의 정수.V는 임의의 정수다.  Lines 2..N+1: 줄마다 항공사가 개방한 도시 이름을 포함한다.도시 명칭은 서쪽에서 동쪽으로 배열되어 있다.두 도시가 같은 경선에 있는 상황은 나타나지 않을 것이다.각 도시의 명칭은 하나의 문자열로 최대 15바이트이며 라틴 자모표의 자모로 구성되어 있다.도시 이름에 빈칸이 없습니다.  Lines N+2..N+2+V-1: 줄마다 두 개의 도시 이름(위 목록의 도시 이름으로 구성)을 포함하고 한 칸으로 나뉜다.이렇게 하면 두 도시 사이의 직항 이중 항로를 나타낸다.  SAMPLE INPUT (file tour.in)8 9 Vancouver Yellowknife Edmonton Calgary Winnipeg Toronto Montreal Halifax Vancouver Edmonton Vancouver Calgary Calgary Winnipeg Winnipeg Toronto Toronto Halifax Montreal Halifax Edmonton Monton Montreal Edmonton Yellow knife Edmonton Calgary OUTPUT FORMAT Line 1: 최적 노선에 따라 방문하는 도시의 수량을 찾을 수 없다.SAMPLE OUTPUT(file tour.out) 7 즉 Vancouver, Edmonton, Montreal, Halifax, Toronto, Winnipeg, Calgary, Vancouver(시작 도시로 돌아가지만 다른 도시 안에 포함되지 않는다). 
문제풀이
여기서 우리가 반대로 되돌아오는 변은 두 가지 다른 경로를 구하는 것이 되었다.우리는 f[i][j]를 사용하여 두 사람이 한 사람이 i번째 도시로 가고 한 사람이 j번째 도시로 가는 경과 도시의 수를 나타낸다.우리가 이동할 때 ij의 가장자리가 f[i][k]에서 지나가지 않을 것을 보증할 수 있다. 왜냐하면 f[i][k]는 j를 고려하지 않았기 때문이다.그리고 우리는 대칭성을 알 수 있다. f[i][j]=f[j][i]는 이렇게 유쾌하게 계속 밀고 마지막에 가장 큰 f[i][n]을 찾으면 된다!
 
코드

/*Author:WNJXYK*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

using namespace std;



#define LL long long



inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}

inline void swap(LL &x,LL &y){LL tmp=x;x=y;y=tmp;}

inline int remin(int a,int b){if (a<b) return a;return b;}

inline int remax(int a,int b){if (a>b) return a;return b;}

inline LL remin(LL a,LL b){if (a<b) return a;return b;}

inline LL remax(LL a,LL b){if (a>b) return a;return b;}



map<string,int> city;

bool g[105][105];

int f[105][105];

int n,m;

int main(){

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++){

		string tmp;

		cin>>tmp;

		city[tmp]=i;

	}

	for (int i=1;i<=m;i++){

		string tmp1,tmp2;

		cin>>tmp1>>tmp2;

		g[city[tmp1]][city[tmp2]]=g[city[tmp2]][city[tmp1]]=true;

	}

	f[1][1]=1;

	for (int i=1;i<=n;i++){

		for (int j=i+1;j<=n;j++){

			for (int k=1;k<j;k++){

				if (g[k][j] && f[i][k]>0 && f[i][k]+1>f[i][j]) f[i][j]=f[j][i]=f[i][k]+1;

			}

		}

	}

	int Ans=1;

	for (int i=1;i<=n;i++){

		if (g[i][n] && f[i][n]>Ans) Ans=f[i][n];

	}

	printf("%d
",Ans);

	return 0;

}

P.S. 오늘 숙제 좀 느리게 했네!BZOJ 제출 48번 남았어요. 다 써요!