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 |
AC了,贡献了一次WA,把rejected写成reject了。DFS,贴代码/** * DFS:由于在遍历时,preTemp会随时变化,因此当找到当前最优解时需要用preBest来保存preTemp */ #include <iostream> #include <cmath> #define MAX_LEN 6 using namespace std; int preTemp[MAX_LEN + 1]; int preBest[MAX_LEN + 1]; int dis[MAX_LEN + 1]; int upper, input; int len; int total; int resType; void init() { int temp = input; //计算输入数据长度 len = 1; while((temp = temp / 10) != 0) len ++; memset(preTemp, 0, sizeof(preTemp)); memset(preBest, 0, sizeof(preBest)); memset(dis, 0, sizeof(dis)); resType = 0; total = 0; } //计算从start开始,长度为dlen的数据的大小,例如对于12345, get(2, 3)返回234 int get(int start, int dlen) { int temp = input, i; int s1 = pow((double)10, len - 1); for(i = 1; i < start; i++) { temp = temp % s1; s1 = s1 / 10; } for(i = 1; i <= len - start + 1 - dlen; i++) temp = temp / 10; return temp; } void solve(int curPos) { //出口条件,超出位数 if(curPos > len) { //已经超出上限,不用考虑 if(dis[curPos - 1] > upper) return; //得到当前最优解 if(dis[curPos - 1] > total) { resType = 2; total = dis[curPos - 1]; //保存分割路径 for(int i = 1; i <= MAX_LEN; i++) preBest[i] = preTemp[i]; } //找到的当前最优解与之前的有重复 else if(dis[curPos - 1] == total && total > 0) resType = 1; return; } int dlen = 0, curVal = 0; //从当前位置向后遍历,逐渐增加当前值的长度 for(dlen = 1; dlen <= len - curPos + 1; dlen++) { //得到当前值 curVal = get(curPos, dlen); //标记临时路径分割前驱 preTemp[curPos + dlen - 1] = curPos; //标记最优值大小 dis[curPos + dlen - 1] = dis[curPos - 1] + curVal; //从下一位开始DFS solve(curPos + dlen); //需要状态还原 preTemp[curPos + dlen - 1] = 0; dis[curPos + dlen - 1] = 0; } } //递归打印路径 void printt(int curPos) { int prePos; if(curPos == 0) return; prePos = preBest[curPos]; printt(prePos - 1); cout<<" "; cout<<get(prePos, curPos - prePos + 1); } //打印结果 void showRes() { if(resType == 0) cout<<"error"<<endl; else if(resType == 1) cout<<"rejected"<<endl; else { cout<<total; printt(len); cout<<endl; } } int main() { while(cin>>upper>>input && (upper != 0 || input != 0)) { init(); solve(1); showRes(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator