| ||||||||||
| 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