dpエクササイズ/エクササイズ
20221 ワード
最近いろいろなことで自分のdpがどれほど弱いかを感じ、dp bzoj 1055 dpを書き始めた[i][j][k]iがjをk没に縮めることができるかどうかを示す
bzoj 1090 dp[i][j]iからjまでの最小距離n 3を列挙し、暴力的に判断すればよい
bzoj 1334翻译人/出题人语死早题意:一つの集合に、このサブセットとsum(a)がすべての和の半分sum(tot)よりも大きく、任意のサブセット内の要素a[i]、sum(a)−a[i]がsum(tot)よりも小さくなるように、サブセットaを选ぶ.位を押さえることができて、書くのがおっくうです
bzoj 3687 interesting dp[i]iが同じ数xorに達するかどうかはコードを見て心を込めて体得する
bzoj 3573この問題は生中継されてコードを書きましたQQQQの1つの重み値は全図の重み値を導いてp[1]=0,p[x]=(この点が1点である場合の重み値はいくらですか)を決定してから、各点は逆にlogを取って並べ替えて、同じ重み値を記録して、答えはn-が最も多い重み値の個数です
bzoj 1369 cljによると、この問題の色は10を超えない.私は5まで運転すれば十分だ.
//Copyright(c)2016 liuchenrui
#include
#define N 255
using namespace std;
char p[]={'W','I','N','G'},s[N],a[4][20][3];
int q[N],t[4],dp[N][N][4];
bool dodp(int l,int r,int k){
if(l==r)return s[l]==p[k];
int &res=dp[l][r][k];
if(res!=-1)return res;
for(int i=1;i<=t[k];i++)
for(int j=l;j<=r-1;j++)
if(dodp(l,j,q[a[k][i][0]])&&dodp(j+1,r,q[a[k][i][1]]))
return res=1;
return res=0;
}
int main(){
freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
memset(dp,-1,sizeof(dp));
q['W']=0;q['I']=1;q['N']=2;q['G']=3;
for(int i=0;i<4;i++){
cin>>t[i];
}
for(int i=0;i<4;i++){
for(int j=1;j<=t[i];j++){
scanf("%s",a[i][j]);
}
}
scanf("%s",s+1);int n=strlen(s+1);
bool flag=0;
for(int i=0;i<4;i++){
if(dodp(1,n,i)){
flag=1,printf("%c",p[i]);
}
}
if(!flag)puts("The name is wrong!");
}
bzoj 1090 dp[i][j]iからjまでの最小距離n 3を列挙し、暴力的に判断すればよい
//Copyright(c)2016 liuchenrui
#include
#define inf 1000000000
#define N 105
using namespace std;
int dp[N][N],n;
char s[N];
int get(int x){
if(x<10)return 1;
if(x==100)return 3;
return 2;
}
int calc(int l1,int r1,int l2,int r2){
if((r2-l2+1)%(r1-l1+1))return inf;
for(int i=l2,j=l1;i<=r2;i++,j++){
if(j==r1+1)j=l1;
if(s[i]!=s[j])return inf;
}
return dp[l1][r1]+2+get((r2-l2+1)/(r1-l1+1)+1);
}
int main(){
freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
scanf("%s",s+1);n=strlen(s+1);
memset(dp,63,sizeof dp);
for(int i=1;i<=n;i++){
dp[i][i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
int l=j,r=i+j-1;
for(int k=l;k1][r]);
dp[l][r]=min(dp[l][r],calc(l,k,k+1,r));
}
}
}
cout<1][n]<
bzoj 1334翻译人/出题人语死早题意:一つの集合に、このサブセットとsum(a)がすべての和の半分sum(tot)よりも大きく、任意のサブセット内の要素a[i]、sum(a)−a[i]がsum(tot)よりも小さくなるように、サブセットaを选ぶ.位を押さえることができて、書くのがおっくうです
//Copyright(c)2016 liuchenrui
#include
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
int dp[100005],a[305],sum,ans,n;
int main(){
//freopen("xxx.in","r",stdin);
//freopen("xxx.out","w",stdout);
splay(n);
for(int i=1;i<=n;i++)splay(a[i]),sum+=a[i];
sort(a+1,a+n+1);dp[0]=1;
for(int i=n;i>=1;i--){
for(int j=sum/2+a[i];j>=a[i];j--){
if(dp[j-a[i]]){
dp[j]=1;ans=max(j,ans);
}
}
}
printf("%d",ans);
}
bzoj 3687 interesting dp[i]iが同じ数xorに達するかどうかはコードを見て心を込めて体得する
//Copyright(c)2016 liuchenrui
#include
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
bitset<2000001>a;
int main(){
int n;splay(n);int x,ans=0;a[0]=1;
for(;n--;)scanf("%d",&x),a^=a<for(int i=1;i<=2000000;i++)if(a[i])ans^=i;
cout<
bzoj 3573この問題は生中継されてコードを書きましたQQQQの1つの重み値は全図の重み値を導いてp[1]=0,p[x]=(この点が1点である場合の重み値はいくらですか)を決定してから、各点は逆にlogを取って並べ替えて、同じ重み値を記録して、答えはn-が最も多い重み値の個数です
//Copyright(c)2016 liuchenrui
#include
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
#define N 500010
int nxt[N*2],fir[N],to[N*2],a[N],sz,d[N],n;
double p[N];
void add(int x,int y){
nxt[++sz]=fir[x],fir[x]=sz,to[sz]=y;
}
void dfs(int x,int fa){
for(int u=fir[x];u;u=nxt[u]){
if(to[u]!=fa){
p[to[u]]=p[x]+log(double(d[x]));
dfs(to[u],x);
}
}
}
int main(){
freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
splay(n);
for(int i=1;i<=n;i++){
splay(a[i]);
}
for(int i=1;iint x,y;splay(x),splay(y);
add(x,y),add(y,x);
d[x]++,d[y]++;
}
for(int i=2;i<=n;i++)d[i]--;
p[1]=0;dfs(1,0);
for(int i=1;i<=n;i++){
p[i]+=log(double(a[i]));
}
sort(p+1,p+n+1);
int now=1,ans=0;
for(int i=1;i<=n;i++){
if(p[i]-p[now]>1e-5){
ans=max(ans,i-now);
now=i;
}
}
ans=max(ans,n-now+1);
cout<
bzoj 1369 cljによると、この問題の色は10を超えない.私は5まで運転すれば十分だ.
//Copyright(c)2016 liuchenrui
#include
#define N 100010
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
int dp[N][6],n,fir[N],nxt[N*2],to[N*2],sz;
void add(int x,int y){
nxt[++sz]=fir[x],fir[x]=sz,to[sz]=y;
}
void dfs(int x,int fa){
for(int u=fir[x];u;u=nxt[u]){
if(to[u]==fa)continue;
dfs(to[u],x);
}
for(int i=1;i<=5;i++){
int cnt=i;
for(int u=fir[x];u;u=nxt[u]){
if(to[u]==fa)continue;
int mi=1<<28;
for(int j=1;j<=5;j++){
if(i!=j){
mi=min(mi,dp[to[u]][j]);
}
}
cnt+=mi;
}
dp[x][i]=cnt;
}
}
int main(){
freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
splay(n);
for(int i=1,x,y;i1,0);
int ans=1<<28;
for(int i=1;i<=5;i++){
ans=min(ans,dp[1][i]);
}
cout<