동적 기획 경전 최우수자 구조 총결

(1)0-1 가방:
만약에 가방이 하나 있다면 총 적재 무게는 Wt이고 n개의 물품이 있으며 모든 물품은 Wi이고 모든 물품의 가치는 Ci이다. 그러면 어떻게 넣어야 이 가방 안의 물건의 가치를 가장 높일 수 있습니까?
dp[i][j]는 이전 i개 아이템 중 적재 무게가 j인 가방에 넣는 최대 가치를 선택하면:
초기화: dp【0】【x】=0;for i=0-》n;j=0-》Wt
dp[i][j]의 값은 dp[i-1][j](첫 번째 아이템은 가방에 넣지 않음), dp[i-1][j-Wi]+Ci(첫 번째 아이템은 가방에 넣지 않음)의 비교적 큰 값이다.
(2) 대가가 있는 최단 경로(동적 기획과 dijkstra 혼합 사용):
점 1에서 점 A 사이의 최단로를 찾지만 점마다 약간의 돈이 소모된다. 이 값은 머니[i]로 돈이 부족하면 길이 통하지 않고 처음에는 돈이 N이 있다는 것을 나타낸다.
dp[i][j]가 i번째 지점까지 가기 위해 j돈의 가장 짧은 경로가 남으면:
dp【x】【y】=inf 초기화;dp【1】【N-money[1]】=0;ifvisited[x][y]=false;ifVisited[1][N-money[1]]=true;

shortest=inf;
moneyLeft=inf;
number=inf;
while(1){
	for(int z=0;z=money[i]&&g[shortest][i]+dp[shortest][moneyLeft]>dp[i][moneyLeft-money[i]]){
dp[i][monetLeft-money[i]]=dp[shortest][moneyLeft]+g[shortest][i];
}
}
}
}
result=max(dp[A][x]);

(3) DP 분할:
m자릿수를 n부분으로 나누고 이 n부분의 곱셈이 가장 크도록 구분법을 요구한다.
규정a[i][j]는 i위에서 j위까지 이 수를 대표한다.
그리고 dp[i][j]는 전 i개수를 대표하고 k부분의 최대 적분으로 나뉜다.
그러면 dp[i][j]=dp[x][k-1]*a[x+1][j]의 최대치, x는 0에서 j-1까지
초기화할 때 dp[x][1]을 a[1][x]로 초기화해야 한다

__int64 number;
//   a   
for(int i=1;i

(4) 숫자를 채우다
몇 가지 정수가 있다고 가정해 보세요. 하나, 둘, 넷...이 수로 정수 N을 만들어 주십시오. 요구하는 수의 수량이 가장 적고, 종류마다 여러 번 사용할 수 있습니다
dp[i]는 숫자 i를 모으는 데 필요한 최소 수량을 나타낸다.
dp[i]=dp[i-1]에서 dp[i-2]까지 dp[i-4]의 최소치를 1.
(5) 조립선 스케줄링.
두 개의 조립 라인이 있는데 1호, 2호로 각 라인마다 N개의 조립 프로세스가 있고 한 제품이 생산하려면 반드시 이 N개의 프로세스를 끝내야 한다. 그러나 모든 프로세스는 1호선이나 2호선에서 조립해야 한다. 각 프로세스에 필요한 시간은Cij이고 제품이 다른 조립 라인에 들어갈 때마다(처음에 조립 라인에 있지 않으면 다른 조립 라인에 들어갈 수도 있다) 소모되는 시간은TIMEij이다. i는 i라인을 대표한다.j는 제j의 절차를 대표하며 전체 조립선의 최소 시간을 구한다.
dp[i][j]는 제i라인에서 제j개의 절차를 완성하는 데 필요한 최소 시간을 대표한다.
그러면 dp[1][j]=min(dp[1][j-1]+C1j, dp[2][j-1]+TIME1j+C1j)
(6) 시퀀스 S와 T 사이의 거리 정의: 삭제, 수정, 문자 거리 증가 +1, 최소 거리는 ST 사이의 거리입니다. ST 사이의 최소 거리를 구합니다.
dp[i][j]는 S전 i개, T전 j개의 최소 거리를 나타낸다
그러면 dp[i][j]=min(dp[i-1][j-1]+(s[i]==t[j])?0:1,dp【i-1】【j】+1,dp【i】【j-1】+1)
(7) 최대 공통 하위 시퀀스
i==jdp[i][j]=dp[i-1][j-1]+1
하면, 만약, 만약...j,그러면 dp[i][j]=max(dp[i][j-1], dp[i-1][j])
소급법 구자 서열:
while(unfinished){
if(s[i]=t[j]) push(s[i]); i--;j--;
else if(dp[i-1][j]가 크다) i---, 그렇지 않으면 j--;
}
(8) 최대 하위 시퀀스
dp【i】=(dp【i-1】>0?)dp【i-1】+string【i】:string【i】
(9) 최장 증자 서열
dp[k]는 앞의 k개의 숫자가 가장 길다는 것을 의미하며, k를 포함한다.
만약number[k]>number[k-1]이면 dp[k]=dp[k+1]+number[k]
그렇지 않으면 꼴찌의 첫 번째가 k보다 작은 것을 앞으로 찾아간다. 예를 들어 A번째라면 dp[k]=max(dp[A]+number[k])