2018/7/19 아날로그
코드
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 5005;
typedef long long LL;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int n,a[MAXN],dp[MAXN],ans;
LL sum[MAXN],last[MAXN];
int main(){
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
n=rd();
for(register int i=1;i<=n;i++){
a[i]=rd();
sum[i]=sum[i-1]+a[i];
}
for(register int i=1;i<=n;i++){
for(register int j=i-1;j>=0;j--)
if(sum[i]-sum[j]>=last[j] && dp[i]<=dp[j]){
dp[i]=dp[j]+1;
last[i]=sum[i]-sum[j];
}
}
printf("%d",n-dp[n]);
return 0;
}
T2인가 dp인가...시험장에서 n번 더 돌았다.굵다실제로는 매우 간단하다. dp[i][j]는 i일째 j의 능력치가 있는 최대 작업 횟수를 나타낸다.업무는 수시로 할 수 있고 횟수를 제한하지 않기 때문에 각 에너지 아래의 최소 근무 시간best[i]를 미리 처리한 다음에 이동하는 데 세 가지 선택이 있다. 첫 번째는 아무것도 하지 않고 두 번째는 수업, 세 번째는 업무, 그리고 바로 전공하면 된다.시간 복잡도 O(S*t)
코드
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 10005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int t,s,n,m,ans;
struct CLASS{
int w,st,ed;
}cla[MAXN];
struct WORK{
int wks,wke;
}wor[MAXN];
vector<int> cnt[MAXN];
int dp[MAXN][105];
int best[10005];
inline bool cmp(WORK A,WORK B){
return A.wkeint main(){
freopen("wrk.in","r",stdin);
freopen("wrk.out","w",stdout);
memset(dp,-0x3f,sizeof(dp));
memset(best,0x3f,sizeof(best));
t=rd();s=rd();n=rd();
for(register int i=1;i<=s;i++) {
cla[i].st=rd();cla[i].ed=rd();cla[i].w=rd();
cnt[cla[i].st].push_back(i);
m=max(m,cla[i].w);
}
for(register int i=1;i<=n;i++){
wor[i].wke=rd();wor[i].wks=rd();
best[wor[i].wke]=min(best[wor[i].wke],wor[i].wks);
}
for(register int i=1;i<=m;i++)
best[i]=min(best[i],best[i-1]);
dp[0][1]=0;
for(register int i=0;ifor(register int j=1;j<=m;j++){
if(i+best[j]<=t)
dp[i+best[j]][j]=max(dp[i+best[j]][j],dp[i][j]+1);
for(vector<int>::iterator k=cnt[i].begin();k!=cnt[i].end();k++){
if(cla[*k].ed+i>t) continue;
int kk=cla[*k].w;
dp[cla[*k].ed+i][kk]=max(dp[cla[*k].ed+i][kk],dp[i][j]);
}
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
}
}
for(register int i=1;i<=m;i++)
ans=max(ans,dp[t][i]);
printf("%d",ans);
return 0;
}
T3 시험장에서 마지막에 시간이 없어요. (제가 40분 늦었다는 qwq를 알려주지 않을 거예요.) n<=10으로 30을 줬어요.정해: 우리는 먼저mid로 나눌 수 있다. 사실 전체 그림은 하나의 국화도이고 하나의 점이 있는데 그것에 각종 체인과 나무를 연결시킨다. 만약에 체인의 상황이라면 이 체인에 필요한 나무 구멍은 사실 이 체인의 포인트 cnt/(2*mid+1)를 위로 정돈하는 것이다.가운데에만 넣으면 좌우 양쪽을 챙길 수 있는mid에 자신까지.그리고 화심을 덮을 수 있는 점들을 하나하나 열거한 다음에 덮을 수 있는 점에 표시를 하고 몇 개의 사슬만 남았다. 그리고 합쳐서 판단한다.시간 복잡도 O (n^2)
코드
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 2005;
const int MAXM = MAXN*MAXN;
const int inf = 0x3f3f3f3f;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int n,head[MAXN],cnt,m,k,ans;
int to[MAXM<<1],nxt[MAXM<<1];
int mx,fl,du[MAXN],sum,ct,dis[MAXN];
bool vis[MAXN];
queue<int> Q;
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
inline void dfs(int x){
vis[x]=1;ct++;
for(register int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u]) continue;
dfs(u);
}
}
inline void find(int x,int Mid){
vis[x]=1;
for(register int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u]) continue;
if(dis[u]==inf) {
ct=0;dfs(u);
sum+=ct/((Mid<<1)+1);
if(ct%((Mid<<1)+1)) sum++;
}
else find(u,Mid);
}
}
inline bool check(int Mid){
for(register int i=1;i<=n;i++){
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
Q.push(i);vis[i]=1;dis[i]=0;sum=0;
while(Q.size()){
int x=Q.front();Q.pop();
for(register int j=head[x];j;j=nxt[j]){
int u=to[j];
if(vis[u] or ((dis[x]+1)>Mid)) continue;
vis[u]=1;dis[u]=dis[x]+1;Q.push(u);
}
}
if(!vis[fl]) continue;
memset(vis,false,sizeof(vis));
find(i,Mid);if(sumreturn true;
}
return false;
}
int main(){
freopen("holes.in","r",stdin);
freopen("holes.out","w",stdout);
n=rd();m=rd();k=rd();
for(register int i=1;i<=m;i++){
int x=rd(),y=rd();
add(x,y);add(y,x);
du[x]++;du[y]++;
if(du[x]>mx) {mx=du[x];fl=x;}
if(du[y]>mx) {mx=du[y];fl=y;}
}
int l=1,r=MAXM;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) {
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}
전재 대상:https://www.cnblogs.com/sdfzsyq/p/9676940.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.