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 |
错了两次,终于发现错误了,贴下代码,没怎么优化,希望给有需要的童鞋#include <iostream> using namespace std; //表示最小值的 long mi[52][52]; //表示最大值的 long ma[52][52]; int n; char edge[52]; int vec[52]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> edge[i-1]; cin >> vec[i]; } edge[n]=edge[0]; long temp; for (int len = 0; len < n; len++) { for (int i = 1; i <= n; i++) { int j=(i+len-1)%n+1; if (len == 0) { mi[i][j] = ma[i][j] = vec[i]; } else { ma[i][j]=-999999; mi[i][j]=999999; int counter=0; while(true){ if(counter==len) break; int k=(i+counter-1)%n+1; int k1=k%n+1; counter++; if (edge[k] == 't') { int temp = ma[i][k] + ma[k1][j]; if (temp > ma[i][j]) ma[i][j] = temp; temp= mi[i][k] + mi[k1][j]; if(temp<mi[i][j]) mi[i][j] = temp; } else { temp = ma[i][k] * ma[k1][j]; if (temp > ma[i][j]) ma[i][j] = temp; if(temp<mi[i][j]) mi[i][j] = temp; temp = ma[i][k] * mi[k1][j]; if (temp > ma[i][j]) ma[i][j] = temp; if(temp<mi[i][j]) mi[i][j] = temp; temp = mi[i][k] * ma[k1][j]; if (temp > ma[i][j]) ma[i][j] = temp; if(temp<mi[i][j]) mi[i][j] = temp; temp = mi[i][k] * mi[k1][j]; if (temp > ma[i][j]) ma[i][j] = temp; if(temp<mi[i][j]) mi[i][j] = temp; } } } } } long max=0; int p; for(int i=1;i<=n;i++){ p=(i+n-2)%n+1; if(ma[i][p]>max) max=ma[i][p]; } cout<<max<<endl; bool head=1; for(int i=1;i<=n;i++){ p=(i+n-2)%n+1; if(ma[i][p]==max) { if(head) { cout<<i; head=0; }else{ cout<<" "<<i; } } } cout<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator