69 条题解
-
1
Sky1231 (sky1231) LV 10 @ 2020-10-14 19:53:59
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; namespace dts { const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; int n,f[101][11][11][11]; char ch[101]; void main() { while (~scanf("%d\n",&n)) { for (int i=1;i<=n;i++) scanf("%c\n",&ch[i]); memset(f,oo_max,sizeof(f)); f[0][0][0][0]=0; for (int i=1;i<=n;i++) { for (int j=0;j<=10;j++) for (int k=0;j+k<=10;k++) for (int l=0;j+k+l<=10;l++) if (ch[i]=='A'&&j>=1) f[i][j][k][l]=min(f[i][j][k][l],f[i-1][j-1][k][l]); else if (ch[i]=='B'&&k>=1) f[i][j][k][l]=min(f[i][j][k][l],f[i-1][j][k-1][l]); else if (ch[i]=='C'&&l>=1) f[i][j][k][l]=min(f[i][j][k][l],f[i-1][j][k][l-1]); for (int j=0;j<=10;j++) for (int k=0;j+k<=10;k++) for (int l=0;j+k+l<=10;l++) { f[i][0][k][l]=min(f[i][0][k][l],f[i][j][k][l]+1); f[i][j][0][l]=min(f[i][j][0][l],f[i][j][k][l]+1); f[i][j][k][0]=min(f[i][j][k][0],f[i][j][k][l]+1); } } printf("%d\n",f[n][0][0][0]); } } } int main() { dts::main(); } -
1
BFS+玄学判重，我确实不太清楚这样的判重有什么用，但是它过了。
#include <bits/stdc++.h> using namespace std; typedef struct { int a[3]={0}; int op=0; int id=0; }hax; int n; char box[100]; queue<hax> que; bool vis[101][11][11][11]={0}; int main() { cin>>n; int i; for(i=0;i<n;i++) { cin>>box[i]; } hax push,now; que.push(push); while(!que.empty()) { now=que.front(); que.pop(); if(now.a[0]+now.a[1]+now.a[2]==0&&now.id==n) { cout<<now.op<<endl; break; } for(;now.a[0]+now.a[1]+now.a[2]<10&&now.id<n;now.id++) { now.a[box[now.id]-'A']++; } for(i=0;i<3;i++) { push=now; if(push.a[i]>0) { push.a[i]=0; push.op++; if(!vis[push.id][push.a[0]][push.a[1]][push.a[2]]) { que.push(push); vis[push.id][push.a[0]][push.a[1]][push.a[2]]=true; } } } } return 0; } -
1
我很喜欢暴力dp，于是就用dp过了这道题
注意到产品只有三种，且每种在某一时刻的数量不超过10，于是就可以开一个四维数组描述当前状态，再用刷表法更新答案
注意枚举产品数量时要从大到小#include<iostream> #include<cstring> using namespace std; char h[160]; int dp[160][12][12][12]; int main() { memset(dp,0x3f,sizeof(dp)); int n,i,u,v,w,k,a=0,b=0,c=0,ans=0,na,nb,nc; cin>>n; for(i=1;i<=n;i++) cin>>h[i]; for(i=1;i<=min(n,10);i++) { if(h[i]=='A') a++; if(h[i]=='B') b++; if(h[i]=='C') c++; } if(n<=10) { if(a) ans++; if(b) ans++; if(c) ans++; cout<<ans; return 0; } dp[10][a][b][c]=0; for(i=10;i<=n;i++) for(u=10;u>=0;u--) for(v=10;v>=0;v--) for(w=10;w>=0;w--) { if(dp[i][u][v][w]!=0x3f3f3f3f) { na=u; nb=v; nc=w; if(u) { na=0; for(k=1;k<=u;k++) { if(i+k>n) break; if(h[i+k]=='A') na++; if(h[i+k]=='B') nb++; if(h[i+k]=='C') nc++; } dp[i+k-1][na][nb][nc]=min(dp[i+k-1][na][nb][nc],dp[i][u][v][w]+1); //cout<<i+k-1<<" "<<na<<" "<<nb<<" "<<nc<<" "<<dp[i+k-1][na][nb][nc]<<endl; } na=u; nb=v; nc=w; if(v) { nb=0; for(k=1;k<=v;k++) { if(i+k>n) break; if(h[i+k]=='A') na++; if(h[i+k]=='B') nb++; if(h[i+k]=='C') nc++; } dp[i+k-1][na][nb][nc]=min(dp[i+k-1][na][nb][nc],dp[i][u][v][w]+1); //cout<<i+k-1<<" "<<na<<" "<<nb<<" "<<nc<<" "<<dp[i+k-1][na][nb][nc]<<endl; } na=u; nb=v; nc=w; if(w) { nc=0; for(k=1;k<=w;k++) { if(i+k>n) break; if(h[i+k]=='A') na++; if(h[i+k]=='B') nb++; if(h[i+k]=='C') nc++; } dp[i+k-1][na][nb][nc]=min(dp[i+k-1][na][nb][nc],dp[i][u][v][w]+1); //cout<<i+k-1<<" "<<na<<" "<<nb<<" "<<nc<<" "<<dp[i+k-1][na][nb][nc]<<endl; } } } cout<<dp[n][0][0][0]; return 0; } -
0
-
0
qq872191552 LV 9 @ 2016-10-04 21:09:57
最近遇到几道这样的题，看起来像dp，其实本质就是BFS+判重...
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#define orz 2000000000
using namespace std;
inline int read( )
{
int sum=0;char c=getchar( );bool f=0;
while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}
while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}
if(f) return -sum;
return sum;
}
inline int getc( )
{
char c=getchar( );
while(c<'A' || c>'C') c=getchar( );
return c-'A'+1;
}
int n,s[105],ans=orz;
int v[4][105][105];
bool vis[105][11][11][11];
struct ex{int dep,pos,a,b,c;}G;
queue<ex>q;
inline void check(int a,int b,int c,int d,int p)
{
if(vis[p][a][b][c]) return;
vis[p][a][b][c]=1;
q.push((ex){d,p,a,b,c});
}
int main( )
{
int i,j,k,a,b,c,d,p;
n=read( );
for(i=1;i<=n;i++) s[i]=getc( );
a=0;b=0;c=0;j=min(n,10);
for(i=1;i<=j;i++)
{
if(s[i]==1) a++;
else if(s[i]==2) b++;
else c++;
}
if(n<=10) {printf("%d",(a>0)+(b>0)+(c>0));return 0;}
q.push((ex){0,10,a,b,c});
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{
for(k=1;k<=3;k++) v[k][i][j]=v[k][i][j-1];
v[s[j]][i][j]++;
}
while(!q.empty( ))
{
G=q.front( );q.pop( );
a=G.a;b=G.b;c=G.c;d=G.dep;p=G.pos;
if(d>=ans) break;
if(p==n) {ans=min(ans,d+(a>0)+(b>0)+(c>0));continue;}
for(i=1;i<=a;i++) {k=min(p+i,n);check(a+v[1][p+1][k]-i,b+v[2][p+1][k],c+v[3][p+1][k],d+1,k);}
for(i=1;i<=b;i++) {k=min(p+i,n);check(a+v[1][p+1][k],b+v[2][p+1][k]-i,c+v[3][p+1][k],d+1,k);}
for(i=1;i<=c;i++) {k=min(p+i,n);check(a+v[1][p+1][k],b+v[2][p+1][k],c+v[3][p+1][k]-i,d+1,k);}
}
printf("%d",ans);
return 0;
} -
0
原题：118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱员grant第1次顺序从流水线上取10个成品（如果一共不足10个，则全部取出），以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持10个成品（如果把剩下的全部取出不足10个，则全部取出），如果所有的成品都装进了箱子，那么grant的任务就完成了。
由于装箱是件非常累的事情，grant希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。（1<=N<=100）
f[i][j][k][l] 表示前i张牌有j张A,k张B，l张C
从当前状态推导
最后扫一遍。var i,j,k,l,n,a,b,c,tmp,ans:longint; z:array[0..100]of char; f:array[0..100,0..10,0..10,0..10]of longint; function min(x,y:longint):longint; begin if x>y then exit(y) else exit(x); end; procedure Init; var i:longint; begin readln(n); for i:=1 to n do readln(z[i]); end; procedure check; var i:longint; begin for i:=1 to 10 do case z[i] of 'A':inc(a); 'B':inc(b); 'C':inc(c); end; if n<=10 then begin writeln(ord(a>0)+ord(b>0)+ord(c>0)); halt; end; end; begin Init; check; fillchar(f,sizeof(f),255); f[10,a,b,c]:=0; for i:=10 to n do for j:=0 to 10 do for k:=0 to 10 do begin l:=10-j-k; if l>=0 then if f[i][j][k][l]>=0 then begin //--------A a:=0; b:=0; c:=0; for tmp:=i+1 to min(n,i+j) do case z[tmp] of 'A':inc(a); 'B':inc(b); 'C':inc(c); end; if f[min(n,i+j),a,k+b,l+c]=-1 then f[min(n,i+j),a,k+b,l+c]:=maxlongint; f[min(n,i+j),a,k+b,l+c]:=min(f[min(n,i+j),a,k+b,l+c],f[i,j,k,l]+1); //---------B a:=0; b:=0; c:=0; for tmp:=i+1 to min(n,i+k) do case z[tmp] of 'A':inc(a); 'B':inc(b); 'C':inc(c); end; if f[min(n,i+k),j+a,b,l+c]=-1 then f[min(n,i+k),j+a,b,l+c]:=maxlongint; f[min(n,i+k),j+a,b,l+c]:=min(f[min(n,i+k),j+a,b,l+c],f[i,j,k,l]+1); //---------C a:=0; b:=0; c:=0; for tmp:=i+1 to min(n,i+l) do case z[tmp] of 'A':inc(a); 'B':inc(b); 'C':inc(c); end; if f[min(n,i+l),j+a,k+b,c]=-1 then f[min(n,i+l),j+a,k+b,c]:=maxlongint; f[min(n,i+l),j+a,k+b,c]:=min(f[min(n,i+l),j+a,k+b,c],f[i,j,k,l]+1); end; end; ans:=maxlongint; for i:=0 to 10 do for j:=0 to 10 do for k:=0 to 10 do if f[n,i,j,k]>=0 then ans:=min(ans,f[n][i][j][k]+ord(i>0)+ord(j>0)+ord(k>0)); writeln(ans); end. -
0
超强状态转移方程
f[10,r[1,10,1],r[1,10,2],r[1,10,3]]:=0;for i:=10 to n do
for j1:=0 to 10 do
for j2:=0 to 10 do
for j3:=0 to 10 do
begin
f[i+r+r+r,
r,j2+r,j3+r]:=
min(
f[i+r+r+r,
r,j2+r,j3+r],
f+1
);
f[i+r+r+r,
j1+r,r,j3+r]:=
min(
f[i+r+r+r,
j1+r,r,j3+r],
f+1
);
f[i+r+r+r,
j1+r,j2+r,r]:=
min(
f[i+r+r+r,
j1+r,j2+r,r],
f+1
);
end; -
0
我果然是菜鸟!!!!!!!!!!
├ 测试数据 01：内存溢出...
├ 测试数据 02：内存溢出...
├ 测试数据 03：内存溢出...
├ 测试数据 04：内存溢出...
├ 测试数据 05：内存溢出...
├ 测试数据 06：内存溢出...
├ 测试数据 07：内存溢出...
├ 测试数据 08：内存溢出...
├ 测试数据 09：内存溢出...
├ 测试数据 10：内存溢出...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：0 有效耗时：0ms
program cboxer;const flag=1023456;
var
f:array[1..100,1..100,1..100,1..100] of integer;
t,a,b,c,i,j,n,best,temp:integer;
ch:char;
d:array[1..100]of integer;
function judge(x,y,z:integer):integer;
begin if (x0)and(y0)and(z0) then judge:=3;
if (x0)and(y=0)and(z0) then judge:=2;
if (x0)and(y0)and(z=0) then judge:=2;
if (x=0)and(y0)and(z0) then judge:=2;
if (x=0)and(y=0)and(z0) then judge:=1;
if (x0)and(y=0)and(z=0) then judge:=1;
if (x=0)and(y0)and(z=0) then judge:=1;
if (x=0)and(y=0)and(z=0) then judge:=0;
end;procedure dfs(i,a,b,c:integer);
var x,y,z:integer;
function judge(x,y,z:integer):integer;
begin if (x0)and(y0)and(z0) then judge:=3;
if (x0)and(y=0)and(z0) then judge:=2;
if (x0)and(y0)and(z=0) then judge:=2;
if (x=0)and(y0)and(z0) then judge:=2;
if (x=0)and(y=0)and(z0) then judge:=1;
if (x0)and(y=0)and(z=0) then judge:=1;
if (x=0)and(y0)and(z=0) then judge:=1;
if (x=0)and(y=0)and(z=0) then judge:=0;
end;
function min(x,y:integer):integer;
begin if x10 then
begin for j:=i+1 to i+a do begin if d[j]=1 then x:=x+1;
if d[j]=2 then y:=y+1;
if d[j]=3 then z:=z+1;
end;
f:=min(temp+1,f); dfs(i+a,x,y,z);
end
else begin for j:=i+1 to n do begin if d[j]=1 then x:=x+1;
if d[j]=2 then y:=y+1;
if d[j]=3 then z:=z+1;
end;
f[n,0,0,0]:=min(temp+judge(x,y,z),f[n,0,0,0]);
end;
end;
if b0 then begin x:=a;y:=0;z:=c; f:=temp+1;
if (n-i)>10 then
begin for j:=i+1 to i+b do begin if d[j]=1 then x:=x+1;
if d[j]=2 then y:=y+1;
if d[j]=3 then z:=z+1;
end;
f:=min(temp+1,f); dfs(i+b,x,y,z);
end
else begin for j:=i+1 to n do begin if d[j]=1 then x:=x+1;
if d[j]=2 then y:=y+1;
if d[j]=3 then z:=z+1;
end;
f[n,0,0,0]:=min(temp+judge(x,y,z),f[n,0,0,0]);
end;
end;
if c0 then begin x:=a;y:=b;z:=0; f:=temp+1;
if (n-i)>10 then
begin for j:=i+1 to i+c do begin if d[j]=1 then x:=x+1;
if d[j]=2 then y:=y+1;
if d[j]=3 then z:=z+1;
end;
f:=min(temp+1,f); dfs(i+c,x,y,z);
end
else begin for j:=i+1 to n do begin if d[j]=1 then x:=x+1;
if d[j]=2 then y:=y+1;
if d[j]=3 then z:=z+1;
end;
f[n,0,0,0]:=min(temp+judge(x,y,z),f[n,0,0,0]);
end;
end;
end;begin
read(n); fillchar(f,sizeof(f),$FF);
for i:=1 to n do
begin read(ch); if (ch='A')then d[i]:=1 else if (ch='B')then d[i]:=2 else if (ch='c')then d[i]:=3;
end;
if n -
0
zhanghanyuan LV 10 @ 2009-11-01 21:00:57
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
明明是数组不够大,却说是超时,晕 -
0
SecretAgent LV 10 @ 2009-10-29 09:15:46
DFS+剪枝终于搞定
编译通过...
├ 测试数据 01：答案正确... 541ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 572ms
├ 测试数据 10：答案正确... 572ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1685ms -
0
var
n,min:integer;
f:array[1..100,0..10,0..10] of byte;
thing:array[1..100] of byte;
procedure init;
var
i,j,k:integer;
ch:char;
begin
readln(n);
for i:=1 to n do
begin
readln(ch);
thing[i]:=ord(ch)-65;
end;
for i:=1 to n do
for j:=0 to 10 do
for k:=0 to 10 do
f:=255;
min:=255;
end;
procedure ni(i,a,b,s,v:integer;var new:integer);
var j,t:integer;
begin
j:=i+1;
while (j0 then ni(i,j,k,f,10-j-k,new);
end;
end;
begin
init;
solve;
writeln(min-1);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
秒杀......
水~~~鉴定完毕 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
呵呵 -
0
最终还是靠自己的努力和记忆化搜索Accepeted了。
思路：
搜索都会写吧。
然后添一个三维数组f，表示在ABC总数分别为i,j,k时的最少搬运次数，若当前ABC总数分别为i,j,k且搬运次数大于（注意是大于而不是大于等于，我因为这样做了而多交了几次）就剪枝。( 2009-9-12 16:44:32 )
___|\__|\__|\__|\__|\__|\_华丽的分割线\__|\__|\__|\__|\__|\__|\__|\__|\_|
谁教我记忆化呀？
我优化后还是70分：
编译通过...
├ 测试数据 01：运行超时...
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：运行超时... ├ 测试数据 10：运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：70 有效耗时：0ms( 2009-9-12 16:04:00 )
-
0
LP.Fighting LV 10 @ 2009-08-19 00:11:26
好可怕的程序...方程那段相当可怕...调了相当久...
注意n
Sky1231 (sky1231)
LV 10
@ 2020-10-14 19:53:59
