Codeforces Round #627 (Div. 3) E&F
26667 단어 codeforces
문제풀이: 선형 dp, f(i, j) f(i, j) f(i, j)는 i번째 임무를 처리하고 j시간에 자는 가장 좋은 답안 총수를 나타낸다.
#include
using namespace std;
int dp[2005][2005], a[2005];
int main(){
int n, h, l, r;
cin >> n >> h >> l >> r;
memset(dp,-0x3f3f3f3f,sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < h; j++){
if((j + a[i]) % h >= l && (j + a[i]) % h <= r){
dp[i][(j+a[i])%h] = max(dp[i][(j+a[i])%h], dp[i-1][j] + 1);
}
else{
dp[i][(j+a[i])%h] = max(dp[i][(j+a[i]) % h], dp[i-1][j]);
}
if((j + a[i] - 1) % h >= l && (j + a[i] - 1) % h <= r){
dp[i][(j+a[i]-1)%h] = max(dp[i][(j+a[i]-1)%h], dp[i-1][j] + 1);
}
else{
dp[i][(j+a[i]-1)%h] = max(dp[i][(j+a[i]-1)%h], dp[i-1][j]);
}
}
}
cout<<*max_element(dp[n],dp[n]+h)<<endl;
return 0;
}
F
문제풀이: 나무의 뿌리를 바꾸다.
#include
using namespace std;
const int N=2e5+7;
int a[N],cnt,head[N],e[N*2],ne[N*2],sz[N],res[N];
void add(int a,int b)
{
e[cnt]=b,ne[cnt]=head[a],head[a]=cnt++;
}
void dfs(int u,int f)
{
int sum=0;
sz[u]=a[u];
for(int i=head[u];~i;i=ne[i]){
int j=e[i];
if(j==f) continue;
dfs(j,u);
sum+=max(0,sz[j]);
}
sz[u]+=sum;
}
void dfs1(int u,int f)
{
res[u]=sz[u];
for(int i=head[u];~i;i=ne[i]){
int j=e[i];
if(j==f) continue;
sz[u]-=max(sz[j],0);
sz[j]+=max(0,sz[u]);
dfs1(j,u);
sz[j]-=max(sz[u],0);
sz[u]+=max(sz[j],0);
}
}
int main()
{
memset(head,-1,sizeof head);
int n; scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",a+i);
if(a[i]==0) a[i]=-1;
}
for(int i=1;i<n;i++){
int a,b; scanf("%d%d",&a,&b);
add(a,b); add(b,a);
}
dfs(1,-1);
dfs1(1,-1);
for(int i=1;i<=n;i++) printf("%d ",res[i]);
puts("");
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.