Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA 了半天终于找出脑残错误,怒贴代码#include<map> #include<set> #include<list> #include<cmath> #include<ctime> #include<queue> #include<cctype> #include<cstdio> #include<string> #include<cassert> #include<climits> #include<cstdlib> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> using namespace std; const double eps=1e-8,pi=acos(-1.0); int cl(double z){return ceil(z-eps);} int flr(double z){return floor(z+eps);} long long cll(double z){return ceil(z-eps);} long long flrl(double z){return floor(z+eps);} int dblcmp(double d){return (d<-eps)?-1:(d>eps);} const int inf=999999999; const long long infl=999999999999999999LL; ///-------------------------------------------------------------------------------------- #define pb push_back #define mp make_pair #define gcd __gcd #define ctz __builtin_ctz #define popcount __builtin_popcount #define gch c=getchar() #define clr(z,w) memset(z,w,sizeof(z)) #define PII pair<int,int> #define PLL pair<long long,long long> #define MII map<int,int> #define MLL map<long long,long long> #define REP(z,a,b) for(int z=(a);z<=(b);z++) #define RREP(z,a,b) for(int z=(a);z>=(b);z--) #define FREP(z,a,b,f) for(int z=(a);z<=(b);z++)if(f) #define CREP(p,z) for(char *p=(z);*p;p++) #define VREP(z,t) for(vector<t>::iterator it=(z).begin();it!=(z).end();++it) #define MREP(z,t1,t2) for(map<t1,t2>::iterator it=(z).begin();it!=(z).end();it++) #define FOR_WORD_IN_LINE gets(buf);string line=buf,word;istringstream in(line);while(in>>word) #define RDS(z) scanf("%s",z) #define RDL(z) scanf("%lld",&z) #define RD1(z) scanf("%d",&z) #define RD2(z,o) scanf("%d%d",&z,&o) #define RD3(z,o,v) scanf("%d%d%d",&z,&o,&v) #define PTS(z) printf("%s\n",z) #define PTL(z) printf("%lld\n",z) #define PT1(z) printf("%d\n",z) #define PT2(z,o) printf("%d %d\n",z,o) #define PT3(z,o,v) printf("%d %d %d\n",z,o,v) #define PTA(arr,a,b) REP(z,a,b)printf("%d%c",arr[z]," \n"[z==b]) #define PTAL(arr,a,b) REP(z,a,b)printf("%lld%c",arr[z]," \n"[z==b]) #define FMT(z,w) do{REP(o,1,w)putchar(z);}while(0) #define DBG(z) do{printf("---------------DEBUG: ");cout<<z<<endl;}while(0) #define FDBG(z,f) do{if(flag)printf("---------------FDEBUG: ");cout<<z<<endl;}while(0) #define JDBG(z,j) do{static int w=0;if(++w%j==0){printf("---------------JDEBUG: ");cout<<z<<endl;}}while(0) template<class T> inline void checkmin(T &a,T b){if(a>b)a=b;} template<class T> inline void checkmax(T &a,T b){if(a<b)a=b;} template<class T> inline bool fcheckmin(T &a,T b){if(a>b){a=b;return true;}else return false;} template<class T> inline bool fcheckmax(T &a,T b){if(a<b){a=b;return true;}else return false;} template<class T> inline double dist(T a,T b){return sqrt(a*1.0*a+b*1.0*b);} //======================================================================================= ///#define U_Set//----------------------------------------------------------------------- #ifdef U_Set const int max_set = 100005; int pos[max_set];int getfather(int i){return (pos[i]==i)?i:(pos[i]=getfather(pos[i]));} void combine(int i,int j){int I=getfather(i),J=getfather(j);if(I!=J)pos[I]=J;} #endif ///#define Trie//------------------------------------------------------------------------ #ifdef Trie struct tnode{tnode *x[26];int id;}; struct trie { tnode pool[255*1005];tnode *root;int top,wd; void nn(tnode *&ptr){if(ptr)return;memset(&pool[++top],0,sizeof(tnode));ptr=&pool[top];} void init(){root=0;top=wd=0;nn(root);}trie(){init();} int insert(char *s){tnode *p=root;for(;*s;s++){int i=*s-'a';nn(p->x[i]);p=p->x[i];}return p->id?p->id:(p->id=++wd);} };trie X; #endif ///#define TreeDP//---------------------------------------------------------------------- #ifdef TreeDP struct node{int id;node *x;}; struct tree { node pool[maxn*3];int tot;void init(int n){tot=n+1;REP(i,0,n)pool[i].x=0;} node *nn(int id,node *x){node *p=&pool[tot++];p->id=id;p->x=x;return p;} void push(int a,int b){pool[a].x=nn(b,pool[a].x);} };tree T; void dfs(Tree &t,int p,int f){for(node *s=t.pool[p].x;s;s=s->x)if(s->id!=f){dfs(t,s->id,p);}} void solve(){int n,a,b;RD1(n);T.init(n);REP(i,1,n-1){RD2(a,b);T.push(a,b);}} #endif ///#define MEM_String//------------------------------------------------------------------ #ifdef MEM_String struct memstring { char mpool[200005];char *mptr[100005];int mtop,mcount; void init(){mtop=mcount=0;}char* getstring(int id){return mptr[id];} void insert(char *w){strcpy(mpool+mtop,w);mptr[++mcount]=mpool+mtop;mtop+=strlen(w)+1;} }; #endif ///#define Directions//------------------------------------------------------------------ #ifdef Directions // ==GRID=={O,R,L,D,U} ==AXIS=={O,U,D,R,L} const int dx[]={0,0, 0,1,-1}; const int dy[]={0,1,-1,0, 0}; #endif ///#define Hashing//--------------------------------------------------------------------- #ifdef Hashing int table[1000005],tsize;///[0,tsize) void init_table(){sort(table,table+tsize);tsize = unique(table,table+tsize)-table;} int get_index(int key){return lower_bound(table,table+tsize,key)-table;} #endif ///#define Primes//--------------------------------------------------------------------- #ifdef Primes const int size=10000005;bool notp[size];int pr[size/10],pn;//int minfac[size]; void getprime() { int i,j;notp[0]=notp[1]=1;for(i=2;i<size;i++){if(!notp[i]){/*minfac[i]=pn;*/pr[pn++]=i;}for(j=0;j<pn;j++){ int x=pr[j]*i;if(x>=size)break;notp[x]=1;/*minfac[x]=j;*/if(i%pr[j]==0)break;}} } #endif ///#define BIT//--------------------------------------------------------------------- #ifdef BIT #define lowbit(z) (z&(-z)) #define TYPE int TYPE c[100005];///注意:size初始化 int size; //c[1..size] void change(TYPE *c,int i,TYPE d){for(;i<=size;i+=lowbit(i))c[i]+=d;} TYPE getsum(TYPE *c,int i){TYPE s=0;for(;i>0;i-=lowbit(i))s+=c[i];return s;} #endif ///====================================================================================== #define INIT_GRAPH(z,a,b) do{REP(i,a,b)REP(j,a,b)z[i][j]=inf;REP(i,a,b)z[i][i]=0;}while(0) #define MCASE do{ int _;scanf("%d",&_);while(_--)solve();}while(0) #define SCASE do{ solve();}while(0) #define pl p<<1 #define pr p<<1|1 inline int pinput(){int S=0,gch;while(!isdigit(c))gch;while(isdigit(c)){S=S*10+c-48;gch;}return S;} //inline int input(){int S=0,flag=1,gch;while(!isdigit(c)&&c!='-')gch;if(c=='-'){flag=0;gch;}while(isdigit(c)){S=S*10+c-48;gch;}return flag?S:-S;} #define LL long long char buf[1000005]; //const int maxn = 100005; //int max_sum[1005][1005]; int a[1005]; int dp1[1005][1005]; int dp2[1005][1005]; //int f1[1005][1005]; //int f2[1005][1005]; void solve() { int n,k; while(RD2(n,k),n) { REP(i,1,n)RD1(a[i]); if(n==k) { puts("Yes"); continue; } REP(i,0,n)REP(j,0,n) { dp1[i][j]=dp2[i][j]=-inf; //f1[i][j] = f2[i][j] =0; } dp1[1][1]=a[1];///must chose //f1[1][1]=1; dp2[1][0]=0;///must not //f2[1][0]=1; REP(i,2,n) { dp2[i][0]=0; //f2[i][0]=1; REP(j,1,i) { dp1[i][j] = max( max(dp1[i-1][j-1],dp2[i-1][j-1]),dp1[i-1][j] ) + a[i]; //if(dp1[i][j] == a[i]+dp1[i-1][j-1])f1[i][j]+=f1[i-1][j-1]; //if(dp1[i][j] == a[i]+dp2[i-1][j-1])f1[i][j]+=f2[i-1][j-1]; //if(dp1[i][j] == a[i]+dp1[i-1][j])f1[i][j]+=f1[i-1][j]; //checkmin(f1[i][j],5); dp2[i][j] = max( dp1[i-1][j], dp2[i-1][j] ); //if(dp2[i][j] == dp1[i-1][j])f2[i][j]+=f1[i-1][j]; //if(dp2[i][j] == dp2[i-1][j])f2[i][j]+=f2[i-1][j]; ////checkmin(f2[i][j],5); } } //PT2(dp1[n][k], dp2[n][k]); if(dp1[n][k]==dp2[n][k]) { puts("No"); continue; } /*if(dp1[n][k]>dp2[n][k]) { puts(f1[n][k]==1?"Yes":"No"); } else { puts(f2[n][k]==1?"Yes":"No"); } continue;*/ int ans = max(dp1[n][k], dp2[n][k]); //if(ans< -inf/2)while(1); int i = n; int j = k; bool dup = false; int must1=false; while(i>1 && j>0) { int dp; if( must1 || dp1[i][j] > dp2[i][j] ) { must1=0; dp=dp1[i][j]-a[i];//if(dp<-inf/2)while(1); int cnt = (dp1[i-1][j-1]==dp)+(dp2[i-1][j-1]==dp)+(dp1[i-1][j]==dp); if(cnt==0)while(1); if(cnt!=1){dup=true; /*printf("ErrorDP1 @ %d %d\n",i,j);*/ break;} if(dp1[i-1][j]==dp){i--;must1=1;} else{i--;j--;} continue; } else if(dp1[i][j] < dp2[i][j] ) { dp=dp2[i][j];//if(dp<-inf/2)while(1); int cnt = (dp1[i-1][j]==dp)+(dp2[i-1][j]==dp); if(cnt==0)while(1); if(cnt!=1){dup=true; /* printf("ErrorDP2 @ %d %d\n",i,j); */break;} i--; continue; } else {dup=true;break;} } if(dup)puts("No"); else puts("Yes"); } } int main(){SCASE;} ///-------------------------------------------------------------------------------------- Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator