낙곡[동태계획3]구간과 환형동태계획
P1220 가로등 끄기
#include
#include
#include
using namespace std;
int n,c,f[60][60][2],sum[60],inf=1e7;
struct lamp{
int p,c;
}s[60];
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>s[i].p>>s[i].c;
sum[i]=sum[i-1]+s[i].c;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j][0]=f[i][j][1]=inf;
}
}
f[c][c][0]=f[c][c][1]=0;
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
f[i][j][0]=min(f[i+1][j][0]+(s[i+1].p-s[i].p)*(sum[n]-(sum[j]-sum[i])),
f[i+1][j][1]+(s[j].p-s[i].p)*(sum[n]-(sum[j]-sum[i])));
f[i][j][1]=min(f[i][j-1][0]+(s[j].p-s[i].p)*(sum[n]-(sum[j-1]-sum[i-1])),
f[i][j-1][1]+(s[j].p-s[j-1].p)*(sum[n]-(sum[j-1]-sum[i-1])));
}
}
cout<<min(f[1][n][0],f[1][n][1])<<endl;
}
P3205 [HNOI2010] 합창팀
#include
#include
using namespace std;
int n,h[1010],mod=19650827,f[1010][1010][2];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
f[i][i][0]=1;
}
for(int len=1;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(h[i]<h[i+1]) f[i][j][0]+=f[i+1][j][0];
if(h[i]<h[j]) f[i][j][0]+=f[i+1][j][1];
if(h[j]>h[j-1]) f[i][j][1]+=f[i][j-1][1];
if(h[j]>h[i]) f[i][j][1]+=f[i][j-1][0];
f[i][j][0]%=mod;f[i][j][1]%=mod;
}
}
cout<<(f[1][n][0]+f[1][n][1])%mod<<endl;
}
P1880 [NOI1995] 스톤 결합
#include
#include
using namespace std;
int n,a[210],sum[210],f[210][210],g[210][210],inf=1e9,maxans,minans=inf;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[n+i]=a[i];
}
for(int i=1;i<=2*n-1;i++){
sum[i]=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=2*n-1;i++){
int j=i+len-1;
g[i][j]=inf;
for(int k=i;k<j;k++){
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]+sum[j]-sum[i-1]);
}
}
}
for(int i=1;i<=n;i++){
maxans=max(maxans,f[i][i+n-1]);
minans=min(minans,g[i][i+n-1]);
}
cout<<minans<<endl<<maxans<<endl;
}
P1063 기운 목걸이
#include
#include
using namespace std;
int head[300],f[300][300];
int n,ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>head[i];
head[n+i]=head[i];
}
for(int len=1;len<=n;len++){
for(int i=1;i+len-1<=2*n-1;i++){
int j=i+len-1;
for(int k=i;k<j;k++){
f[i][j]=max(f[i][j],head[i]*head[k+1]*head[j+1]+f[i][k]+f[k+1][j]);
}
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;
}
P1005 매트릭스 취수 게임(60점)
#include
#include
#include
using namespace std;
int n,m,a[90];
long long dp[90][90],sum,ans;
long long quick_pow(long long a,long long x){
long long ans=1;
while(x){
if(x&1) ans=ans*a;
a=a*a;
x>>=1;
}
return ans;
}
int main(){
cin>>n>>m;
while(n--){
memset(dp,0,sizeof dp);
ans=0;
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=m;i++){
for(int j=m;j>=i;j--){
long long x=quick_pow(2,m-(j-i)-1);
dp[i][j]=max(dp[i][j],max(dp[i-1][j]+x*a[i-1],dp[i][j+1]+x*a[j+1]));
}
}
for(int i=1;i<=m;i++){
ans=max(ans,dp[i][i]+quick_pow(2,m)*a[i]);
}
sum+=ans;
}
cout<<sum<<endl;
}
P3146 [USACO16OPEN]248 G
#include
#include
using namespace std;
int n,a[250],f[250][250],ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];f[i][i]=a[i];
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=i;k<j;k++){
if(f[i][k]==f[k+1][j]){
f[i][j]=max(f[i][j],f[i][k]+1);
ans=max(ans,f[i][j]);
}
}
}
}
cout<<ans<<endl;
}
P4170 [CQOI2007] 페인팅
[i] [j] [j] f[i] [j] [i] [i, j] [i, j] [i, j] f[i] f[i] [j] [i] [j] f[i] [i] [i, j] [i, j] [i, j] [i, j] [i,]의 최소 도색 횟수 f[i] [j] = f [i] [j] [j] = = = = = i = = = = j m i = [i] [j] [i] [i] [i] [i] [i] [i] [i] [j] [i] [j] [j] [f[i] [j] [j] [f[i] [j] [j] [j] [j] [j] [j] [j] [j] [{\begin{aligned} 1, i=j\min(f[i+1][j], f[i][j-1], s[i]=s[j]\min(f[i][k]+f[k+1][j]), k\in[i,j-1],s[i]eq s[j]\end{aligned}\right. f[i][j]=⎩⎪⎨⎪⎧1,i==jmin(f[i+1][j],f[i][j−1],s[i]==s[j]min(f[i][k]+f[k+1][j]),k∈[i,j−1],s[i]=s[j]
#include
#include
#include
using namespace std;
string s;
int n,f[60][60],inf=1e9;
int main(){
cin>>s;n=s.length();s.insert(0," ");
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=inf;
}
}
for(int i=1;i<=n;i++){
f[i][i]=1;
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(s[i]==s[j]) f[i][j]=min(f[i+1][j],f[i][j-1]);
else{
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
}
}
}
cout<<f[1][n]<<endl;
}
CF607B Zuma
#include
#include
using namespace std;
int n,a[600],f[600][600],inf=2e9;
void init(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=inf;
}
}
for(int i=1;i<=n;i++){
f[i][i]=1;
}
for(int i=1;i<n;i++){
if(a[i]==a[i+1]) f[i][i+1]=1;
else f[i][i+1]=2;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
init();
for(int len=3;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(a[i]==a[j]) f[i][j]=f[i+1][j-1];
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
}
cout<<f[1][n]<<endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제11회 산동성 대학생 프로그램 설계 경연대회 Adventurer's Guild(dp)전송문 제목: 몬스터의 수량 n, 캐릭터의 생명력 H, 캐릭터의 공격 S 건네기;다음 n행, 매 행위 매 몬스터의 혈액량 h, 공격 s, 가치 w; 매번 몬스터를 처치할 때마다 h의 혈액량과 s의 공격을 소모한다. ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.