首页 > 专题系列 > Java解POJ > POJ 2295 A DP Problem [解题报告] Java
2013
11-11

POJ 2295 A DP Problem [解题报告] Java

A DP Problem

问题描述 :

In this problem, you are to solve a very easy linear equation with only one variable x with no parentheses! An example of such equations is like the following:

2x – 4 + 5x + 300 = 98x


An expression in its general form, will contain a ‘=’ character with two expressions on its sides. Each expression is made up of one or more terms combined by ‘+’ or ‘-’ operators. No unary plus or minus operators are allowed in the expressions. Each term is either a single integer, or an integer followed by the lower-case character x or the single character x which is equivalent to 1x.

You are to write a program to find the value of x that satisfies the equation. Note that it is possible for the equation to have no solution or have infinitely many. Your program must detect these cases too.

输入:

The first number in the input line, t (1 <= t <= 10) is the number of test cases, followed by t lines of length at most 260 each containing an equation. There is no blank character in the equations and the variable is always represented by the lower-case character x. The coefficients are integers in the range (0...1000) inclusive.

输出:

The output contains one line per test case containing the solution of the equation. If s is the solution to the equation, the output line should contain [s] (the floor of s, i.e., the largest integer number less than or equal to s). The output should be IMPOSSIBLE or IDENTITY if the equation has no solution or has infinite solutions, respectively. Note that the output is case-sensitive.

样例输入:

2 
2x-4+5x+300=98x
x+2=2+x

样例输出:

3
IDENTITY

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args) throws Exception{
  BufferedReader scanner=new BufferedReader(new InputStreamReader(System.in));
  int n=Integer.parseInt(scanner.readLine());
  String f;
  String[] t;
  double a1,a2,b1,b2;
  for (int i=0;i< n ;i++ ){
	a1=0;
	a2=0;
	b1=0;
	b2=0;
	f=scanner.readLine();
	t=f.split("=");
	String e="";
	char oper='+';
	for (int j=0;j< t[0].length() ;j++ ){
		if (t[0].charAt(j)=='-'||t[0].charAt(j)=='+'){
			if (e.charAt(e.length()-1)=='x'){
				if (e.equals("x")){
					e="1x";
				}
		  a1=a1+Double.parseDouble(oper+e.substring(0,e.length()-1));
			}
			else{
				b1=b1+Double.parseDouble(oper+e);
			}
			oper=t[0].charAt(j);
			e="";
		}
		else{
			if (t[0].charAt(j)!=' '){
				e=e+t[0].charAt(j);
			}
		}
	}
	if (!e.equals("")){
		if (e.charAt(e.length()-1)=='x'){
			if (e.equals("x")){
				e="1x";
			}
	  a1=a1+Double.parseDouble(oper+e.substring(0,e.length()-1));
		}
		else{
			b1=b1+Double.parseDouble(oper+e);
		}
	}
	e="";
	oper='+';
	for (int j=0;j< t[1].length() ;j++ ){
		if (t[1].charAt(j)=='-'||t[1].charAt(j)=='+'){
			if (e.charAt(e.length()-1)=='x'){
				if (e.equals("x")){
					e="1x";
				}
	          a2=a2+Double.parseDouble(oper+e.substring(0,e.length()-1));
			}
			else{
				b2=b2+Double.parseDouble(oper+e);
			}
			e="";
			oper=t[1].charAt(j);
		}
		else{
			if (t[1].charAt(j)!=' '){
				e=e+t[1].charAt(j);
			}
		}
	}
	if (!e.equals("")){
		if (e.charAt(e.length()-1)=='x'){
			if (e.equals("x")){
				e="1x";
			}
		a2=a2+Double.parseDouble(oper+e.substring(0,e.length()-1));
		}
		else{
			b2=b2+Double.parseDouble(oper+e);
		}
	}
	if (a1==a2){
		if (b1==b2){
			System.out.println("IDENTITY");
		}
		else{
			System.out.println("IMPOSSIBLE");
		}
	}
	else{
	  System.out.println((int)Math.floor((b2-b1)/(a1-a2)));
	}
  }
 }
}

  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?