CodeForces - 1096D Easy Problem(선형 dp)

1663 단어 동적 기획
제목 링크: 클릭하여 보기
제목의 뜻: 문자열을 주십시오. 모든 문자에 하나의 값이 있습니다. 현재 값과 최소한의 문자를 삭제해야 합니다. 문자열에 하위 서열 '하드' 가 포함되지 않는 것을 만족시켜야 합니다.
제목 분석: 선형 dp, 그러나 나는 할 줄 모른다. 문제를 보고 쓴 것은 먼저 dp[i][1]를 i번째 문자까지 문자열에'h'를 포함하지 않는 최소 비용으로 하고 dp[i]를 i번째 문자까지 문자열에 서열'하'를 포함하지 않는 최소 비용으로 유추하여 dp[i]4]까지 간다. 그러면'하'의 이동을 예로 들자.만약 우리가 i번째 위치에 하위 서열'하'를 포함하지 않으려면 전 i-1개의 위치에 하위 서열'하'를 포함하지 않고 이동하거나 현재 위치의 문자'r'를 삭제해서 이동할 수 있기 때문에 전이 방정식은 다음과 같다.

dp[ i ][ j ] = min( dp[ i - 1 ][ j - 1 ] ,dp[ i - 1 ][ j ] + cost[ i ] )


정답은 dp[n][4]입니다.
코드:
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e5+100;

char s[N],str[]=" hard";

LL a[N],dp[N][5];

int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n;
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;i++)
		scanf("%lld",a+i);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='h')
			dp[i][1]=dp[i-1][1]+a[i];
		else
			dp[i][1]=dp[i-1][1];
	}
	for(int j=2;j<=4;j++)
		for(int i=1;i<=n;i++)
		{
			if(s[i]==str[j])
				dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+a[i]);
			else
				dp[i][j]=dp[i-1][j];
		}
	printf("%lld
",dp[n][4]);
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}

HUNNU11409(디지털 dp)
NVIDIA SDK Manager로 Jetson 설치

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage