HDU 4283 You Are the One(12 년 천진 구간 DP)

전재 출처 를 밝 혀 주 십시오.감사합니다.http://blog.csdn.net/acm_cxlove/article/details/7854526       by-cxlove 제목:한 대열 이 있 습 니 다.모든 사람 에 게 분노 치 D 가 있 습 니 다.만약 에 그 가 K 번 째 로 등장 한다 면 불쾌 지 수 는(K-1)*D 입 니 다.그러나 옆 에 작은 오 두 막 이 있어 서 어느 정도 출전 절 차 를 조정 할 수 있다.http://acm.hdu.edu.cn/showproblem.php?pid=4283  제목 은 오래 봤 는데 이해 가 안 돼~~~QQ.주 의 는 어느 정도 조정 되 었 습 니 다.즉,스 택 에 들 어 가 는 순서 가 확정 되 었 습 니 다.첫 번 째 반응 의 욕심 은 틀 렸 을 것 입 니 다.스 택 의 영향 을 받 아 스 택 의 상 태 를 유지 해 야 한다 고 생각 하여 끊 었 습 니 다~~~사실은 하나의 구간 DP 입 니 다.dp[i][j]는 i 개인 에서 j 개인 까지 이 구간 의 최소 비용(이 j-i+1 명 만 고려 한 것 입 니 다.앞 에 몇 명 이 있 는 지 고려 할 필요 가 없다)그러면 dp[i][j]의 i 번 째 사람 에 게 는 첫 번 째 출전 이 가능 하고 j-i+1 번 째 출전 도 가능 하 다.K 번 째 등 판 즉 i+1 이후 K-1 이 먼저 등 판 한 것 을 고려 하면 키 문제 가 발생 했다.k+1 개 뒤에 있 기 때문에 전체 분노 치 는 k*(sigma(i+k-j)를 더 해 야 합 니 다.
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#define inf 1<<27
#define N 105
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define LL long long
using namespace std;
int dp[105][105];
int val[105],sum[105];
int main(){
	int n,t,cas=0;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		sum[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&val[i]);
			sum[i]=sum[i-1]+val[i];
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				dp[i][j]=inf;
		for(int l=1;l<=n-1;l++){
			for(int i=1;i<=n-l;i++){
				int j=i+l;
				//dp[i][j]=min(dp[i][j],dp[i+1][j]+sum[j]-sum[i]);
				for(int k=i;k<=j;k++)
					dp[i][j]=min(dp[i][j],val[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j]);
			}
		}
		printf("Case #%d: %d
",++cas,dp[1][n]);
	}
	return 0;
}
wed.xml에서 Filter,servlet 설정 형식
[위 에]Chapter 2 User Authentication,Authorization,and Security(9):로그 인 이름과 사용자 가 메타 데 이 터 를 보 는 것 을 방지 합 니 다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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